【动态规划】似包非包
似包非包
1.组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
题目分析：
看完题目要求，在看示例1，你可能会想到这是一个完全背包问题。但是如果这道题真的问的是组合的话，前面出现 (1，1，2) 后面就不会出现(1，2，1) 和 (2，1，1)这样的情况。题目把这三种情况当成了不同的情况。也就是顺序不一样它们也是属于不同组合。
但是实际上 排列 和 组合 是不一样的，排列是有序的，组合是无序的。
如果这道题问题的是组合，也就不考虑选出来数的顺序，那(1，1，2) 、(1，2，1) 、 (2，1，1)就只属于一种情况，不管它是什么组合。
而排序是有序的，要保证选出来数的先后顺序。
所以这道题应该叫做排列总和才对。
算法原理：
实质上背包问题都是解决这一类问题：有限制条件下的 “组合” 问题
从状态表示
dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j，所有的选法中，最大的价值
来看，我们的状态表示从来没有规定过挑选的顺序。而只是在两个限定条件下，所有的选法中，要最大价值即可。
因此我们挑选出来的所有选法都是没有顺序的。所以背包问题实质上解决的 “组合” 问题。
当用背包问题去解决方案数的时候，其实求的是 ''组合" 数。而这道题问的是组合数实际上求的是排序数。所以这道题不能用背包问题解决。
我们就用常规的状态表示来分析这道题。
1.状态表示
这里我们学一种新的状态表示法。之前做的大多数问题都是用的是线性dp或者区间dp来解决，所以之前的经验都是以某个位置为结尾，巴拉巴拉。或者以某个位置为起点，巴拉巴拉。或者选取一段区间巴拉巴拉。
但是这道题既不像线性dp也不像区间dp，我们可以这样来：
根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示。
接下来以一个例子来说什么是重复子问题。比如这道题，给我们一堆数假设是[a、b、c、d]，然后看看凑成target，一共有多少种排列数。如果要看排列数一定要看看每个位置怎么选，因为每个位置选数要考虑先后顺序。假设凑成target需要四个位置，第一个位置可以选[a、b、c、d]、第二个位置也可以选[a、b、c、d]…，如果第一个位置放了a，那接下来就看剩下的位置凑出来target - a。重复的问题是本来想要的是整个区间凑成target，然后固定一个数之后发现整个区间凑成target - a 就可以了。也就是说我们的相同问题是看凑成一个数有多少种方法。本来想看凑成target有多少种方法，接下来就是去看target - a 有多少种方法。这就是重复子问题。
接下来将重复子问题，抽象出来一个状态表示。想看一个数有多少种话，我们搞一个一维数组。
dp[i] 表示：凑成总和为 i，一共有多少种排列数。
本来想看凑成target有多少种方法，接下来发现固定完一个数就是去看target - a 有多少种方法。这就是根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
2.状态转移方程
如果能用上面那种方式定义状态表示，其实状态转移方程就和上面一模一样。
我们用一条线长度表示target。我们细贯用最后一个位置划分情况。
假设最后一个位置的数是nums[j]（0 <= j <= n.size()) 表示数组里任意一个数都可以放到最后一个位置。
如果最后一个位置放的是nums[j]，整体想凑成总和 i ，那仅需看看前
