【动态规划】似包非包

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 ，那仅需看看前面区间凑成 i - nums[j] 一共有多少排列数。那最后仅需把 nums[j] 放到每种排列数的的后面就可以了。也就是之前有多少种方法加nums[j]，依旧有多少种方法。而一个nums[j] 就对应一个dp[i - nums[j]]，因此我们的状态转移方程

但是这里要注意 i - nums[j] 不一定存在，所以用这个状态必须要保证 i >= nums[j]

3.初始化

因为我们会用到之前的状态，所以我们把第一个位置初始化，当 i = 0 表示想凑成0这个数一共有多少种方案，这道题所有数据都是大于等于1，因此想凑成0，选一个空集就可以。因此dp[0] = 1

4.填表顺序

从左往右

5.返回值

dp[i] 表示：凑成总和为 i，一共有多少种排列数。我们要的是凑成target，一共有多少种排列数。因此返回dp[target]。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {

        vector<double> dp(target + 1);
        dp[0] = 1;
        for(int i = 1; i <= target; ++i)
            for(int j = 0; j < nums.size(); ++j)
                if(i >= nums[j])
                    dp[i] += dp[i - nums[j]];
        return dp[target];

    }
};

2.不同的二叉搜索树

题目链接： 96. 不同的二叉搜索树

题目分析：

二叉搜索树要求：左子树 < 根 < 右子树

算法原理：

1.状态表示

根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示。

如果是按照这样一个方式定义出来一个状态表示，一旦写出来之后，你会发现状态转移方程和你分析得到状态表示的过程是一样的。

假设我们有1、2、3、4、5, 5个节点，我们要求的是5个结点的时候一共有多少种二叉搜索树。如果把3号结点当作根节点 ，左子树是不是有2个结点，右子树也有两个结点。其实状态表示已经出来了。之前想看5个结点的时候一共有多少种二叉搜索树，但是当我固定完一个根节点之后，如固定3号结点为根，问题就变成了，左子树两个结点有多少二叉搜索树，右子树两个结点有多少二叉搜索树。

重复问题就是，当结点个数为某个数的时候，一共有多少二叉搜索树。

dp[i] 表示：结点个数为 i 的时候，一共有多少种二叉搜索树

2.状态转移方程

其实状态转移方程就和状态表示怎么来的非常一样。

如果结点个数为 i 个的时候。从 1 、2、 … 、 i，这个时候我们可以任选一个数当根结点，假设当根节点为 j（1 <= j <= i），那它的左子树一共有多少节点，右子树一共有多少节点呢? 因为1 <= j <= i，所有可以得到左子数下标[1，j - 1]，右子树下标
[j +1，i]，因为都是闭区间求个数的时候最终都要加1，所以左子树结点个数 j - 1 - 1 + 1 = j - 1，右子树结点个数 i - j - 1 + 1 = i - j。然后问题就变成了只要找到二叉搜索树的个数和右边二叉搜索树的个数，然后把它们乘起来，那么整个二叉搜索树的个数就是 dp[j-1] * dp[i-j] 。也就是当 j 做根节点二叉搜索树的个树dp[j-1] * dp[i-j] 。

当结点个数为 i 的时候，将所有根结点 j（ 1 <= j <= i）二叉搜索树的个数加起来，就是结点个数为 i 的二叉搜索树个数。

其实这个状态转移方程就是卡特兰数的一个递推公式，卡特兰数可以用来解决不同的二叉搜索树有多少个，也可以解决括号匹配等等。。。

3.初始化

因为我们会用到 dp[j-1] 和 dp[i-j] 它们是小于dp[i]的，所有我们把dp[0]初始化，dp[0] 表示：结点个数为 0 的时候，一共有多少种二叉搜树。空树也是一个二叉搜索树，所以dp[0] = 1。还有一种解释如果dp[0]不等于1，后面递推公式里面的值都是0。

4.填表顺序

从左往右

5.返回值

dp[i] 表示：结点个数为 i 的时候，一共有多少种二叉搜索树。题目问的结点个数为n的时候，有多少种二叉搜索树，所以返回dp[n]

class Solution {
public:
    int numTrees(int n) {

        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)//枚举根节点
                dp[i] += dp[j - 1] * dp[i - j];
        return dp[n];
    }
};