【动态规划】似包非包

似包非包

• 1.组合总和 Ⅳ
• 2.不同的二叉搜索树

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]，整体想凑成总和