6. 动态规划
复现代码随想录DP专题
卡尔哥的文章真的很好，思路十分清晰，我照着他的路线，把他提及的题目刷了一遍，也写了点自己的理解，仅供参考。
一、套路
动态规划五部曲
确定dp数组以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
打印数组（与自己的推导比较，看哪里错了）
二、DP基础
1. 斐波那契数（LeetCode-509）
题目
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
思路
这题很简单，我试着用五部曲练练手
dp[i] 的意义为：第 i 个数的斐波那契数值为 dp[i]
d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ]
dp[0]=0 dp[1]=1
根据递推公式可知，dp[i] 依赖它的前两个元素，所以一定是从前往后遍历
推导一下前十项 0 1 1 2 3 5 8 13 21 34 55
代码展示
class Solution { public: int fib(int n) { vector<int> dp(35); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } };
但其实还可以优化，因为dp[i] 只依赖它的前两个元素，只需维护两个元素，没有必要写出整个数组，浪费了空间
class Solution { public: int fib(int n) { vector<int> dp(3); dp[0] = 0; dp[1] = 1; if (n < 2) { return dp[n]; } int result; for (int i = 2; i <= n; i++) { result = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = result; } return result; } };
2. 爬楼梯（LeetCode-70）
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
思路
第⼀层楼梯再跨两步就到第三层 ，第⼆层楼梯再跨⼀步就到第三层。 所以到第三层楼梯的状态可以由第⼆层楼梯和到第⼀层楼梯状态推导出来
五部曲
dp[i] 定义：爬到第 i 阶有 dp[i] 种方法
d p [ i ] = d p [ i − 2 ] + d p [ i − 1 ]
dp[1]=1 dp[2]=2 正整数不用考虑 dp[0]
肯定从前往后
前五项 1 2 3 5 8
代码展示
class Solution { public: int climbStairs(int n) { // 这步忘记了，导致n=1时访问不到dp[2] if (n<=1) { return n; } vector<int> dp(n + 1); dp[1] = 1, dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; cout << dp[i]; } return dp[n]; } };
也是可以优化，滚动数组优化空间
class Solution { public: int climbStairs(int n) { if (n <= 2) { return n; } vector<int> dp(3); dp[1] = 1, dp[2] = 2; int result; for (int i = 3; i <= n; i++) { result = dp[1] + dp[2]; dp[1] = dp[2]; dp[2] = result; } return result; } };
3. 使用最小花费爬楼梯（LeetCode-746）
题目
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999
思路
五部曲
定义： 爬到第 i 个台阶的最低花费为 dp[i]
当前台阶的最低花费与 i-1 和 i-2 台阶有关，应该是从（ i-1 台阶最低消费+从 i-1 台阶向上爬的费用）和（i-2 台阶最低消费+从 i-2 台阶向上爬的费用） 中取较小值
d p [ i ] = m i n ( ( d p [ i − 1 ] + c o s t [ i − 1 ] ) , ( d p [ i − 2 ] + c o s t [ i − 2 ] ) )
初始值 dp[0]=0 dp[1]=0
显然从前往后
示例一应该是 dp[N]={0,0,10,15}
代码展示
class Solution { public: int minCostClimbingStairs(vector<int> &cost) { int N = cost.size() + 1; vector<int> dp(N); for (int i = 2; i < N; i++) { dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2])); } return dp[N-1]; } };
这题还是可以滚动数组优化
class Solution { public: int minCostClimbingStairs(vector<int> &cost) { int N = cost.size() + 1; vector<int> dp(2); int result; for (int i = 2; i < N; i++) { result = min((dp[1] + cost[i - 1]), (dp[0] + cost[i - 2])); dp[0] = dp[1]; dp[1] = result; } return result; } };
4. 不同路径（LeetCode-62）
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28 1 2 示例 2： 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109
思路
五部曲继续
dp[m][n] 含义：到达m行n列有 dp[m][n] 条路径
机器人每次只能向下或向右移动，所以该点路径条数只与它上面和左边的点有关，是它们路径条数之和
d p [ m ] [ n ] = d p [ m − 1 ] [ n ] + d p [ m ] [ n − 1 ]
初始化时，最左边一列和最上面一行的值肯定为1
要先有 − 1才能有你，肯定正序
略
代码展示
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n)); for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } };
可以滚动数组优化，可以看出，我们计算是以行为单位一行一行计算的，其实该点值只和它上一行有关，所以创建一个长度为网格列数的数组
d p [ j ] = d p [ j ] + d p [ j − 1 ]
dp[j-1] 最初是欲计算点上左侧的值，被计算后，数值的含义下移，变成欲计算点左侧的值。同理 dp[j] 在计算之前代表欲计算点上侧的值
class Solution { public: int uniquePaths(int m, int n) { vector<int> dp(n); for (int i = 0; i < n; i++) { dp[i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } };
5. 不同路径Ⅱ（LeetCode-63）
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
思路
五部曲
dp[m][n] 含义：到达m行n列有 dp[m][n] 条路径
机器人每次只能向下或向右移动，所以该点路径条数只与它上面和左边的点有关，是它们路径条数之和。这里比先前的题多了障碍，所以障碍这点的 dp 值为零
初始化时，最左边一列和最上面一行的值肯定为1。但要注意如果有障碍，那么那点 dp 值要为零。还要注意只要有一个障碍，那它后面的值不用算了，肯定为零
要先有 − 1才能有你，肯定正序
略
代码展示
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n)); for (int i = 0; i < m; i++) { if (obstacleGrid[i][0] == 0) { dp[i][0] = 1; } else { dp[i][0] = 0; break; } } for (int i = 0; i < n; i++) { if (obstacleGrid[0][i] == 0) { dp[0][i] = 1; } else { dp[0][i] = 0; break; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 0) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } else { dp[i][j] = 0; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cout << dp[i][j] << " "; } cout << endl; } return dp[m - 1][n - 1]; } };
6. 整数拆分（LeetCode-343）
题目
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
思路
拆数字 i ，可以得到的最大乘积为 dp[i]
可能会是两数相乘所得，也有可能是三数及以上相乘所得。这里就分两种情况取较大值即可。
变量 i 从 1 遍历到 n-1 ，两数相乘情况下结果为 i ∗ ( n − i ) ，三数及以上相乘情况下结果为 i ∗ d p [ n − i ]。这里的 dp[n-i] 是拆分数字 n-i 的最大乘积，其实是已经拆分过的，它就已经是几个数相加等于 n-i 的情况了，这点要理解，主要是想明白数组的含义
d p [ n ] = m a x ( i ∗ ( n − i ) , i ∗ d p [ n − i ] )
dp[2]=1
先有 dp[n-i] 再有 dp[n] ，所以从前往后
测试用例
代码展示
class Solution { public: int integerBreak(int n) { vector<int> dp(n + 1); dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j < i - 1; j++) { // max函数只能两两比较 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])); } } return dp[n]; } };
7. 不同的二叉搜索树（LeetCode-96）
题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
思路
这里用代码随想录的图分析一下
n = 1
n = 2
n = 3
可以分3种情况
1.元素1为头结点时，没有比1小的元素了，所以左子树为空，右子树元素个数为二，就有 dp[2] 种组合。为什么是 dp[2] 种，题目不是说是由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种吗？这里呢其实大家要明白 dp[i] 的含义，也就是先定dp数组——i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种。我这里去掉了节点值从 1 到 n ，因为对于元素个数为2的二叉搜索树来说，无论它的元素值是 1 ， 2 还是 2 ， 3 ，排列组合的结果都是一样的！
2.元素2为头结点时，左子树元素个数为一，右子树元素个数也为一
3.元素3为头结点时，左子树元素个数为二，右子树元素个数也为零
4.所以 d p [ 3 ] = d p [ 2 ] ∗ d p [ 0 ] + d p [ 1 ] ∗ d p [ 1 ] + d p [ 0 ] ∗ d p [ 2 ]
五部曲
dp[i] 含义： i 个不同元素节点组成的互不相同的二叉搜索树有 dp[i] 种
变量 j 从 0 遍历至 i-1 ，dp[i] 初值为零
d p [ i ] = d p [ i ] + d p [ j ] ∗ d p [ i − j − 1 ]
dp[0]=1 从定义上来讲，空节点也是⼀颗⼆叉树，也是⼀颗⼆叉搜索树
节点数为i的状态是依靠 i之前节点数的状态,所以从前往后
测试用例
代码展示
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 = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; } };
8. 小结
卡尔哥的方法是真的好用，写dp代码没多少，主要是五部曲写出思路。代码随想录yyds！
三、背包三讲
01背包
有N件物品和⼀个最多能被重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装⼊背包里物品价值总和最大？
1. 例题（二维数组解法）
题目
背包最大重量为4
| 重量 | 价值 |
|
| 物品0 | 1 |
15 |
| 物品1 | 3 |
20 |
| 物品2 | 4 |
30 |
问：背包能背的物品最大价值是多少？
思路
五部曲
数组含义
使用二维数组 dp[i][j]，含义：从下标为 [ 0 ∼ i ] 的物品中任意取，放入容量为 j 的背包，价值总和最大为多少
递推公式由两个方向推出
一、不放物品 i 的最大价值
背包容量为 j，但不放物品 i时的最大价值，即 dp[i-1][j]
二、放物品 i 的最大价值
先找到 dp[i-1][j-weight[i]]，含义：i − 1 保证了不放物品 i ，背包容量为 j − w e i g h t [ i ] 其实就是为了给后续放物品 i一个预留量，保证放了物品 i 后背包不会溢出，所以最大价值为 dp[i-1][j-weight[i]]+value[i]
递推公式：
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] )
数组初始化
背包容量 j jj 为零时，显然价值为零
只选物品0，即第一行，显然只要物品0重量小于等于背包重量 j jj，价值就为物品0的价值，否则为零
确定遍历顺序
先遍历背包还是物品都可以
dp[i][j] 所需的数据在其左上方
测试用例
代码展示
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_2_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1)); for (int i = 1; i < bagWeight + 1; i++) { if (weight[0] <= i) { dp[0][i] = value[0]; } } for (int j = 1; j < bagWeight + 1; j++) { for (int i = 1; i < weight.size(); i++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } } cout << dp[weight.size() - 1][bagWeight]; } int main() { test_2_wei_bag_problem1(); return 0; }
2. 例题（滚动数组解法）
还是之前的例子，可以用滚动数组将数组降为一维
dp[i][j]=max(dp[i−1][j],dp[i−1][j−weight[i]]+value[i])
由递推公式得： dp[i][j] 只和它的上一行有关，且有关元素的行数为 i − 1 i-1i−1，列数 ≤ j \le j≤j。那么我们就可以将数组压缩成一维
dp[i−1][j−weight[i]] |
dp[i−1][j] |
欲求元素 |
看这张表，如果数组是一维的情况，那么在算出欲求元素后，其实是将欲求元素覆盖掉 dp[i-1][j]，并且我们的遍历顺序也要改变。在二维情况下，我们是按从左到右的顺序求的，但在一维中，必须从右向左！因为在求欲求元素时，我们要保证 dp[i-1][j-weight[i]] 未被覆盖！同时，必须按照先遍历物品，再嵌套遍历背包的顺序。
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次
举例：
假设物品0重量 w e i g h t [ 0 ] = 1，价值 v a l u e [ 0 ] = 15
如果是正序遍历
d p [ 1 ] = d p [ 1 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 15
d p [ 2 ] = d p [ 2 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 30
在第一行运行后 d p [ 1 ] 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 d p [ 1 ]，意味着物品0被放了两次。
那么为什么之前在写二维数组的时候是正序的？
因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_1_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1); for (int i = 0; i < weight.size(); i++) { for (int j = bagWeight; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight]; } int main() { test_1_wei_bag_problem1(); return 0; }
3. 分割等和子集（LeetCode-416）
题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
思路
完全背包和01背包区别？
完全背包中一个商品可以放 无数次
01背包中一个商品只能放一次
本题如何套？
分割成两个子集且元素和相等，即背包容量为 s u m / 2
物品重量为 n u m s [ i ]，价值也为 n u m s [ i ]
背包正好装满，就说明找到了 s u m / 2
五部曲
dp[i] 含义
背包容量为 i 时，最大可以凑出的子集和
递推公式
本题中，物品重量为 n u m s [ i ] ，价值也为 n u m s [ i ] n
d p [ j ] = m a x ( d p [ j ] , d p [ j − n u m s [ i ] ] + n u m s [ i ] )
数组初始化
都初始化为零
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序，不懂的回看例题
测试用例
代码展示
class Solution { public: bool canPartition(vector<int> &nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2) { return false; } int target = sum / 2; vector<int> dp(target + 1); for (int i = 0; i < nums.size(); i++) { for (int j = target; j >= nums[i]; j--) { dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); if (dp[target] == target) { return true; } } } return false; } };
对比卡尔哥的解法，用 target+1 做为数组大小，优化了空间。遍历中遇到一个吻合的直接返回 true，优化了时间。
4. 最后一块石头的重量Ⅱ（LeetCode-1049）
题目
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40] 输出：5
示例 3：
输入：stones = [1,2] 输出：1
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
思路
如何套？
目的是求 最小的可能重量，其实也就是凑重量尽可能相等的两堆。举个例子 10，1，2，2，2，2，2 。我们就可以分为重量为 11 1111 和 10 1010 的两堆。
五部曲
dp[j] 含义
重量为 j jj 的背包最大可以装的石头重量和
递推公式
本题中，物品重量为 s t o n e s [ i ] ，价值也为 s t o n e s [ i ]
d p [ j ] = m a x ( d p [ j ] , d p [ j − s t o n e s [ i ] ] + s t o n e s [ i ] )
数组初始化
设默认值零即可
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
代码展示
class Solution { public: int lastStoneWeightII(vector<int> &stones) { int sum = accumulate(stones.begin(), stones.end(), 0); int target = sum / 2; vector<int> dp(target + 1); for (int i = 0; i < stones.size(); i++) { for (int j = target; j >= stones[i]; j--) { dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); } } return sum - dp[target] - dp[target]; } };
开始时没有考虑到问题是最小的可能重量。在 stones = [31,26,33,21,40] 这个样例中：一堆为 31，26，21 重量和为 78，另一堆为 33，40 重量和为 73 。按照代码求法，target=75。求的是 dp[75]。为什么不是求 dp[73]？回看数组定义：重量为 j jj 的背包最大可以装的石头重量和。可以看出：其实 dp[75] 与 dp[73] 是相等的
5. 目标和（LeetCode-494）
题目
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1 输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路
怎么套？
分成两堆， l e f t − r i g h t = t a r g e t
又因为 l e f t + r i g h t = s u m
所以 l e f t = ( s u m + t a r g e t )/ 2
这和以前遇到的题目 不一样
先前：容量为 i 的背包，最多能装多少？
这次：填满容量为 i 的背包，有多少种方法？
五部曲
数组定义
dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
递推公式
分两种情况，一种是不包含当前物品的方法数量，另一种是包含当前物品的方法数量。我们要求的就是二者 之和。为了方便，直接使用一维数组展示：
d p [ j ] = d p [ j ] + d p [ j − n u m s [ i ] ]
数组初始化
如果是二维数组，也就是要初始化第一行，即只有物品零的情况，可以想见，填满背包容量为零的方法有一种，就是不装东西。但填满不为零的背包的方法却为零，除非物品重量等于背包容量。所以在一维数组中初始化应该是 dp[0]=1 其他为0
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
代码展示
class Solution { public: int findTargetSumWays(vector<int> &nums, int target) { int sum = accumulate(nums.begin(), nums.end(), 0); if ((sum < target) || ((sum + target) % 2) || ((sum + target) < 0)) { return 0; } int left = (sum + target) / 2; vector<int> dp(left + 1); dp[0] = 1; for (int i = 0; i < nums.size(); i++) { for (int j = left; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return dp[left]; } };
6. 一和零（LeetCode-474）
题目
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100
思路
五部曲
dp[i][j] 含义
最多能装 i 个 0 和 j 个 1 的背包的最大子集的数量
递推公式
虽然是二维的，但其实只包含背包重量这一个方面，本质还是滚动数组。
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − n u m Z e r o ] [ j − n u m O n e ] + 1 )
其中，n u m Z e r o 和 n u m O n e 分别表示当前物品，即当前子集的零和一个数。相当于物品的重量。而后面的加一相当于物品的价值。为什么是一？因为加上当前物品后，最大子集数量就加一了。
数组初始化
物品价值不为负数，所以初始化为零即可
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
本图为最后状态
代码展示
class Solution { public: int findMaxForm(vector<string> &strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int idx = 0; idx < strs.size(); idx++) { int numZero = 0, numOne = 0; for (char val : strs[idx]) { if (val == '0') { numZero++; } else { numOne++; } } for (int i = m; i >= numZero; i--) { for (int j = n; j >= numOne; j--) { dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1); } } } return dp[m][n]; } };
完全背包
1. 例题
题目
有N件物品和一个最多能背重量为 W 的背包。第 i ii 件物品的重量是w e i g h t [ i ] 得到的价值是 v a l u e [ i ] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中，我依然举这个例子：
背包最大重量为4.
物品为：
| 重量 | 价值 | |
| 物品0 | 1 |
15 |
| 物品1 | 3 |
20 |
| 物品2 | 4 |
30 |
每件商品都有无限个
问：背包能背的物品最大价值是多少？
思路
01背包和完全背包唯一不同在于遍历顺序上
01背包核心代码
for(int i = 0; i < weight.size(); i++) // 遍历物品 { for(int j = bagWeight; j >= weight[i]; j--) // 遍历背包容量 { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次
举例：
假设物品0重量 w e i g h t [ 0 ] = 1 ，价值 v a l u e [ 0 ] = 15
如果是正序遍历
d p [ 1 ] = d p [ 1 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 15
d p [ 2 ] = d p [ 2 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 30
在第一行运行后 d p [ 1 ] 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 d p [ 1 ] ，意味着物品0被放了两次。
那么为什么之前在写二维数组的时候是正序的？
因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！
而完全背包的物品是可以添加多次的，所以要从小到大去遍历
for(int i = 0; i < weight.size(); i++) // 遍历物品 { for(int j = weight[i]; j >= bagWeight; j++) // 遍历背包容量 { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
遍历顺序是否强制先遍历物品，再遍历背包容量？
在01背包的一维数组中必须先遍历物品，再遍历背包容量。
而在完全背包的一维数组中，循环嵌套顺序却无所谓。
因为 dp[j] 是根据它同行的左边的元素推出来的，而无论哪种顺序，它的左值都是更新过的，可用的。
但先后顺序可以颠倒的前提是纯完全背包问题！题目变化的可能就不行
代码展示
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_CompletePack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1); for (int i = 0; i < weight.size(); i++) { for (int j = weight[i]; j <= bagWeight; j++) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight]; } int main() { test_CompletePack(); return 0; }
2. 零钱兑换Ⅱ（LeetCode-518）
题目
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
思路
本题要点：
硬币有无限个，所以完全背包问题
本题要求凑成总金额的个数
五部曲
dp[j] 含义
凑成总金额为 j的硬币组合数（背包的容量为 j的背包恰好装满的方法数）
递推公式
d p [ j ] = d p [ j ] + d p [ j − c o i n s [ i ] ]
数组初始化
dp[0]=1 从数组含义看：凑成总金额为零的硬币组合数为一
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要正序
本题不是纯完全背包问题，不能交换顺序。因为本题求的是组合数，要求元素之间没有顺序。
测试用例
代码展示
class Solution { public: int change(int amount, vector<int> &coins) { vector<int> dp(amount + 1); dp[0] = 1; for (int i = 0; i < coins.size(); i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } };
3. 组合总和Ⅳ（LeetCode-377）
题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
由示例一最后一行得，题目看似求的组合数，实际上求的是排序数
五部曲
dp[j] 含义
凑成目标正整数为 j jj 的排列个数（使背包容量为 j jj 的背包恰好装满的组合数——不同排序算做不同组合）
递推公式
d p [ j ] + = d p [ j − d p [ n u m s ] ]
数组初始化
dp[0]=1
遍历顺序
先遍历背包，嵌套遍历物品，且物品遍历要正序
如果把遍历 nums（物品）放在外循环，遍历target的作为内循环的话，举⼀个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有 {3,1} 这样的集合，因为nums遍历放在外层，3只能出现在1后面
代码展示
class Solution { public: int combinationSum4(vector<int> &nums, int target) { vector<int> dp(target + 1); dp[0] = 1; for (int j = 0; j <= target; j++) { for (int i = 0; i < nums.size(); i++) { if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) { dp[j] += dp[j - nums[i]]; } } } return dp[target]; } };
4. 爬楼梯（改写成完全背包）
题目
原题为LeetCode-70，是一道简单动态规划，现改写为：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 m 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路
一步爬一个或两个或三个或 m 个就是物品，楼顶就是背包，其实就是问装满背包的方法有多少种。再想这是排序数还是组合数？明显先2后1（先爬2阶楼梯再爬1阶楼梯）和先1后2是不同的方法，所以求的是排序数，那么就要求先遍历背包，嵌套遍历物品
五部曲
dp[j] 含义
爬到有 j个台阶的楼顶的方法数
递推公式
d p [ j ] + = d p [ j − i ]
数组初始化
dp[0]=1
遍历顺序
上文已说明
代码实现
class Solution { public: int climbStairs(int n, int m) { vector<int> dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= n; i++) { // 遍历背包 for (int j = 1; j <= m; j++) { // 遍历物品 if (i - j >= 0) dp[i] += dp[i - j]; } } return dp[n]; } };
代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了
5. 零钱兑换（LeetCode-322）
题目
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3 输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
思路
五部曲
dp[j] 含义
凑成总金额为 j 所需的最少硬币数
递推公式
求最少硬币数，一种就是不含当前物品（这里说的当前物品就是指当前的这枚硬币，假如当前硬币值为2，不是说背包里就不含硬币值为2的硬币了，因为是硬币无限枚，所以很可能有，而是说不含当前这枚硬币值为2的硬币）的硬币数，数值保持不变。另一种是含当前物品的硬币数，数值要加一（加上当前物品）
d p [ j ] = m i n ( d p [ j ] , d p [ j − c o i n s [ i ] ] + 1 )
数组初始化
凑成总金额为2的硬币数肯定为零，而其他要初始化为最大值，不然在运行递推公式时初始值会覆盖 d p [ j − c o i n s [ i ] ] + 1
遍历顺序
这里求最少硬币数量，硬币是组合数还是排列数都无所谓，所以顺序随意
代码实现
class Solution { public: int coinChange(vector<int> &coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < coins.size(); i++) { for (int j = coins[i]; j <= amount; j++) { // 如果dp[j - coins[i]]是初始值则跳过 if (dp[j - coins[i]] != INT_MAX) { dp[j] = min(dp[j], dp[j - coins[i]] + 1); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; } };
易错点在 d p [ j − c o i n s [ i ] ] 是初始值没有跳过，还有记得没有任何一种硬币组合能组成总金额，返回 -1
6. 完全平方数（LeetCode-279）
题目
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 104
思路
看到示例一的 4 + 4 + 4 知道是完全背包问题，本题求和为 n 的完全平方数的最少数量
五部曲
dp[j] 含义
和为 j jj 的完全平方数的最少数量
递推公式
想一下，如果访问的当前物品是完全平方数，那么就分别求装它和不装它的数量，二者取小值。如果不是完全平方数，那么还是取不装它的数量
d p [ j ] = m i n ( d p [ j ] , d p [ j − i ] + 1 )
数组初始化
和为 0 的完全平方数的最少数量肯定为零，而其他要初始化为最大值
遍历顺序
这里求最少数量，是组合数还是排列数都无所谓，所以顺序随意
代码展示
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { bool flag = false; if (i == 1) { flag = true; } for (int k = 0; k < i; k++) { if (k * k == i) { flag = true; break; } } for (int j = i; j <= n; j++) { if (flag && dp[j - i] != INT_MAX) { dp[j] = min(dp[j], dp[j - i] + 1); } } } return dp[n]; } };
分析一下，很快写出来了。但时间复杂度过于之高。那肯定是求完全平方数没有处理好。看了下题解，是我的物品选错了，我是遍历数然后判断它是不是完全平方数，但这样做就烦了。数值 n 什么时候完全平方数？说白了 n 是整数。那我的物品就取 n
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { for (int j = i * i; j <= n; j++) { dp[j] = min(dp[j], dp[j - i * i] + 1); } } return dp[n]; } };
7. 单词拆分（LeetCode-139）
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同
思路
不会，卡尔哥的也没看懂。然后发现官方题解很清晰
我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 s[0~i-1] 中的分割点 j ，看 s[0~j-1] 组成的字符串 S 1
（默认 j = 0 时 S 1
为空串）和 s[j~i-1] 组成的字符串 S 2
是否都合法，如果两个字符串均合法，那么按照定义 S 1 和 S 2
拼接成的字符串也同样合法。由于计算到 dp[i] 时我们已经计算出了 dp[0~i−1] 的值，因此字符串 S 1
是否合法可以直接由 dp[j] 得知，剩下的我们只需要看 S 2
是否合法即可，因此我们可以得出如下转移方程
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
五部曲
dp[i] 含义
表示字符串前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词
递推公式
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
数组初始化
dp[0]=true 表示字符串为空，但题目中说了“给定⼀个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。
遍历顺序
实在是没看懂，直接复制卡尔哥的原话了
题⽬中说是拆分为⼀个或多个在字典中出现的单词，所以这是完全背包。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题最终要求的是是否都出现过，所以对出现单词集合⾥的元素是组合还是排列，并不在意！
那么本题使⽤求排列的⽅式，还是求组合的⽅式都可以。
即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。
但本题还有特殊性，因为是要求⼦串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。（如果不理解的话，可以⾃⼰尝试这么写⼀写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。
测试用例
代码展示
class Solution { public: bool wordBreak(string s, vector &wordDict) { unordered_set wordset(wordDict.begin(), wordDict.end()); vector dp(s.size() + 1, false); dp[0] = true; for (int i = 0; i <= s.size(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };
