1、动态规划理论基础

动态规划刷题大纲
image.png

1.1、什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
在关于贪心算法，你该了解这些！(opens new window)中我举了一个背包问题的例子。

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
所以贪心解决不了动态规划的问题。

其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。
而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。
大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。
上述提到的背包问题，后序会详细讲解。

1.2、动态规划的解题步骤

做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp[i]表示的是什么。
这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。
状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
因为一些情况是递推公式决定了dp数组要如何初始化！

后面的讲解中我都是围绕着这五点来进行讲解。
可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。

其实 确定递推公式 仅仅是解题里的一步而已！
一些同学知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。
后序的讲解的大家就会慢慢感受到这五步的重要性了。

1.3、动态规划应该如何debug

相信动规的题目，很大部分同学都是这样做的。
看一下题解，感觉看懂了，然后照葫芦画瓢，如果能正好画对了，万事大吉，一旦要是没通过，就怎么改都通过不了，对 dp数组的初始化，递推公式，遍历顺序，处于一种黑盒的理解状态。

写动规题目，代码出问题很正常！
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

一些同学对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。
这是一个很不好的习惯！

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
这也是我为什么在动规五步曲里强调推导dp数组的重要性。

举个例子哈：在「代码随想录」刷题小分队微信群里，一些录友可能代码通过不了，会把代码抛到讨论群里问：我这里代码都已经和题解一模一样了，为什么通过不了呢？
发出这样的问题之前，其实可以自己先思考这三个问题：

  • 这道题目我举例推导状态转移公式了么？
  • 我打印dp数组的日志了么？
  • 打印出来了dp数组和我想的一样么？

如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

然后在问问题，目的性就很强了，群里的小伙伴也可以快速知道提问者的疑惑了。
注意这里不是说不让大家问问题哈， 而是说问问题之前要有自己的思考，问题要问到点子上！
大家工作之后就会发现，特别是大厂，问问题是一个专业活，是的，问问题也要体现出专业！

如果问同事很不专业的问题，同事们会懒的回答，领导也会认为你缺乏思考能力，这对职场发展是很不利的。
所以大家在刷题的时候，就锻炼自己养成专业提问的好习惯。

1.4、总结

这一篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何debug。
动态规划是一个很大的领域，今天这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础。
在后序讲解中针对某一具体问题，还会讲解其对应的理论基础，例如背包问题中的01背包，leetcode上的题目都是01背包的应用，而没有纯01背包的问题，那么就需要在把对应的理论知识讲解一下。
大家会发现，我讲解的理论基础并不是教科书上各种动态规划的定义，错综复杂的公式。
这里理论基础篇已经是非常偏实用的了，每个知识点都是在解题实战中非常有用的内容，大家要重视起来哈。
今天我们开始新的征程了，你准备好了么？

2、斐波那契数列

509. 斐波那契数

image.png
image.png

这道题其实可以用递归来做，但是使用递归算法之前，应该先了解递归算法关于时间复杂度的计算
带你逐步分析递归算法的时间复杂度 —> 卡哥写的，分析的很好我觉得！
递归算法的空间复杂度 —> 这篇讲的也很好，例题也刚好是斐波那契数列

思路

递归

  1. class Solution {
  2. public:
  3.     int getFn(int n){
  4.         if(n == 0) return 0;
  5.         if(n == 1) return 1;
  6.         else{
  7.             return getFn(n - 1) + getFn(n - 2);
  8.         }
  9.     }
  11.     int fib(int n) {
  12.         return getFn(n);
  13.     }
  14. };
  • 时间复杂度O(2^n)
  • 空间复杂度O(n) —> 开辟了栈空间

动态规划

  1. 确定dp数组以及下标的含义
    1. dp[i] 的定义为：第 i 个斐波那契数列值是 dp[i]
  2. 确定递推公式
    1. dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化
    1. dp[0] = 0; dp[1] = 1;
  4. 确定遍历顺序
    1. 从前向后
  5. 举例推导dp数组
  1. class Solution {
  2. public:
  3.     int fib(int n) {
  4.         if(n <= 1) return n;
  5.         int dp[2];
  6.         dp[0] = 0;
  7.         dp[1] = 1;
  8.         int sum = 0;
  9.         for(int i = 2; i <= n; i++){
  10.             sum = dp[0] + dp[1];
  11.              dp[0] = dp[1];
  12.              dp[1] = sum;
  13.         }
  14.         return sum;
  15.     }
  16. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

3、爬楼梯

70. 爬楼梯

image.png

思路

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
我们来分析一下，动规五部曲：
定义一个一维数组来记录不同楼层的状态

  1. 确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

  1. 确定递推公式

如果可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。
这体现出确定dp数组以及下标的含义的重要性！

  1. dp数组如何初始化

在回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]中方法。
那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但都基本是直接奔着答案去解释的。
例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。
但总有点牵强的成分。

那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.

其实这么争论下去没有意义，大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。
从dp数组定义的角度上来说，dp[0] = 0 也能说得通。

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。
所以本题其实就不应该讨论dp[0]的初始化！

我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。
所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

  1. 确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

  1. 举例推导dp数组

举例当n为5的时候，dp table（dp数组）应该是这样的
image.png
如果代码出问题了，就把dp table 打印出来，看看究竟是不是和自己推导的一样。
此时大家应该发现了，这不就是斐波那契数列么！
唯一的区别是，没有讨论dp[0]应该是什么，因为dp[0]在本题没有意义！

以上五部分析完之后，C++代码如下：

版本1：

  1. // 版本一
  2. class Solution {
  3. public:
  4.     int climbStairs(int n) {
  5.         if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
  6.         vector<int> dp(n + 1);
  7.         dp[1] = 1;
  8.         dp[2] = 2;
  9.         for (int i = 3; i <= n; i++) { // 注意i是从3开始的
  10.             dp[i] = dp[i - 1] + dp[i - 2];
  11.         }
  12.         return dp[n];
  13.     }
  14. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

版本2

  1. class Solution {
  2. public:
  3.     int climbStairs(int n) {
  4.         if(n == 1) return 1;
  5.         else if(n == 2) return 2;
  7.         int dp[2];
  8.         dp[0] = 1;
  9.         dp[1] = 2;
  10.         int step = 0;       // 当前所在的台阶数
  11.         for(int i = 3; i <= n; i++){
  12.             step = dp[0] + dp[1];
  13.             dp[0] = dp[1];
  14.             dp[1] = step;
  15.         }
  16.         return step;
  17.     }
  18. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

版本1才是动态规划原汁原味的模样，体现了动态规划的思考逻辑。

4、使用最小花费爬楼梯

746. 使用最小花费爬楼梯

image.png
image.png

思路

这道题目可以说是昨天动态规划：爬楼梯(opens new window)的花费版本。
注意题目描述：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯
所以示例1中只花费一个15 就可以到阶梯顶，最后一步可以理解为 不用花费。
读完题大家应该知道指定需要动态规划的，贪心是不可能了。

  1. 确定dp数组以及下标的含义

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）
对于dp数组的定义，大家一定要清晰！

  1. 确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
那么究竟是选dp[i-1]还是dp[i-2]呢？
一定是选最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值

  1. dp数组如何初始化

根据dp数组的定义，dp数组初始化其实是比较难的，因为不可能初始化为第i台阶所花费的最少体力。
那么看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。
所以初始化代码为：

  1. vector<int> dp(cost.size());
  2. dp[0] = cost[0];
  3. dp[1] = cost[1];
  1. 确定遍历顺序

最后一步，递归公式有了，初始化有了，如何遍历呢？
本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。
因为是模拟台阶，而且dp[i]又dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来。
例如：01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？ 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢？
这些都是遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的！

  1. 举例推导dp数组

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：
image.png
如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。
以上分析完毕，整体C++代码如下：

  1. // 版本一
  2. class Solution {
  3. public:
  4.     // 默认第一步需要花费，最后一步不需要花费
  5.     int minCostClimbingStairs(vector<int>& cost) {
  6.         vector<int> dp(cost.size());
  7.         dp[0] = cost[0];
  8.         dp[1] = cost[1];
  10.         for(int i = 2; i < cost.size(); i++){
  11.             dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
  12.         }
  13.         // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
  14.         return min(dp[cost.size() - 1], dp[cost.size() - 2]);
  15.     }
  16. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

还可以优化空间复杂度，因为dp[i] 就是由前两位推出来的，那么也不用dp数组了，C++代码如下：

  1. class Solution {
  2. public:
  3.     // 默认第一步需要花费，最后一步不需要花费
  4.     int minCostClimbingStairs(vector<int>& cost) {
  5.         int dp[2];
  6.         dp[0] = cost[0];
  7.         dp[1] = cost[1];
  8.         int dpi = 0;
  9.         for(int i = 2; i < cost.size(); i++){
  10.             dpi = min(dp[0], dp[1]) + cost[i];
  11.             dp[0] = dp[1];
  12.             dp[1] = dpi;
  13.         }
  14.         // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
  15.         return min(dp[0], dp[1]);
  16.     }
  17. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

5、动态规划周总结

动态规划 - 5. 动态规划周总结

6、不同路径

62. 不同路径 - 力扣（LeetCode）
image.png
image.png

思路

深搜

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。
注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！
如图举例：
image.png
此时问题就可以转化为求二叉树叶子节点的个数，代码如下：

  1. class Solution {
  2. public:
  3.     int dfs(int i, int j, int m, int n){
  4.         if(i > m || j > n) return 0;        // 越界了就不算
  5.         if(i == m && j == n) return 1;      // 找到一种路径
  6.         return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
  7.     }
  9.     int uniquePaths(int m, int n) {
  10.         return dfs(1, 1, m, n);
  11.     }
  12. };

大家如果提交了代码就会发现超时了！
来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。
这棵树的深度其实就是m+n-1（深度按从1开始计算）。
那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）
所以上面深搜代码的时间复杂度为$O(2^{m + n - 1} - 1)$，可以看出，这是指数级别的时间复杂度，是非常大的。

动态规划

机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

  1. 确定递推公式

想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

  1. dp数组的初始化

如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
所以初始化代码为：

  1. for (int i = 0; i < m; i++) dp[i][0] = 1;
  2. for (int j = 0; j < n; j++) dp[0][j] = 1;
  1. 确定遍历顺序

这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

  1. 举例推导dp数组

如图所示：
image.png

使用二维数组（重点掌握！）

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         vector<vector<int>> dp(m, vector(n, 0));
  5.         for(int i = 0; i < m; i++){
  6.             dp[i][0] = 1;
  7.         }
  8.         for(int j = 0; j < n; j++){
  9.             dp[0][j] = 1;
  10.         }
  11.         for(int i = 1; i < m; i++){
  12.             for(int j = 1; j < n; j++){
  13.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  14.             }
  15.         }
  16.         return dp[m - 1][n - 1];
  17.     }
  18. };
  • 时间复杂度：$O(m × n)$
  • 空间复杂度：$O(m × n)$

使用一维数组（可以理解为滚动数组）

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         vector<int> dp(n);
  5.         for (int i = 0; i < n; i++) dp[i] = 1;
  6.         for (int j = 1; j < m; j++) {
  7.             for (int i = 1; i < n; i++) {
  8.                 dp[i] += dp[i - 1];
  9.                 // 不能理解的话就打日志
  10.                 cout << "dp[" << i << "]-->" << dp[i] << "   ";
  11.             }
  12.             cout << endl;
  13.         }
  14.         return dp[n - 1];
  15.     }
  16. };
  • 时间复杂度：$O(m × n)$
  • 空间复杂度：$O(n)$

数论方法

在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。
image.png
在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。
那么有几种走法呢？ 可以转化为，给你m + n - 2个不同的数，随便取m - 1个数，有几种取法。
那么这就是一个组合问题了。
那么答案，如图所示：
image.png
求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。
例如如下代码是不行的。

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         int numerator = 1, denominator = 1;
  5.         int count = m - 1;
  6.         int t = m + n - 2;
  7.         while (count--) numerator *= (t--); // 计算分子，此时分子就会溢出
  8.         for (int i = 1; i <= m - 1; i++) denominator *= i; // 计算分母
  9.         return numerator / denominator;
  10.     }
  11. };

需要在计算分子的时候，不断除以分母，代码如下：

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         long long numerator = 1; // 分子
  5.         int denominator = m - 1; // 分母
  6.         int count = m - 1;
  7.         int t = m + n - 2;
  8.         while (count--) {
  9.             numerator *= (t--);
  10.             while (denominator != 0 && numerator % denominator == 0) {
  11.                 numerator /= denominator;
  12.                 denominator--;
  13.             }
  14.         }
  15.         return numerator;
  16.     }
  17. };
  • 时间复杂度：$O(m)$
  • 空间复杂度：$O(1)$

计算组合问题的代码还是有难度的，特别是处理溢出的情况！

7、不同路径 II

63. 不同路径 II - 力扣（LeetCode）

image.png
image.png

思路：
如果做过 62. 不同路径 - 力扣（LeetCode）的话，那么这道题的思路就非常明确了。
动规五部曲是一样的逻辑。至于题目中的障碍物，如果遇到了障碍物说明这条路径走不通了，那么应该让障碍物保持初始状态，即0.

有难点的就是：dp数组的初始化，如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
image.png
下标（0，j）的初始化情况同理
所以本题的初始化为：

  1. vector<vector<int>> dp(m, vector<int>(n, 0));
  2. for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
  3. for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理

整体C++代码如下：

  1. class Solution {
  2. public:
  3.     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
  4.         int row = obstacleGrid.size();      // 行
  5.         int col = obstacleGrid[0].size();   // 列
  6.         vector<vector<int>> dp(row, vector(col, 0));
  7.         for(int i = 0; i < row && obstacleGrid[i][0] == 0; i++){
  8.             dp[i][0] = 1;
  9.         }
  10.         for(int j = 0; j < col && obstacleGrid[0][j] == 0; j++){
  11.             dp[0][j] = 1;
  12.         }
  13.         for(int i = 1; i < row; i++){
  14.             for(int j = 1; j < col; j++){
  15.                 if(obstacleGrid[i][j] == 0){    // 没有障碍物的时候才推导
  16.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  17.                 }
  18.             }
  19.         }
  20.         return dp[row - 1][col - 1];
  21.     }
  22. };
  • 时间复杂度：$O(n × m)$，n、m 分别为obstacleGrid 长度和宽度
  • 空间复杂度：$O(n × m)$

8、拆分整数

343. 整数拆分 - 力扣（LeetCode）

image.png

思路

动态规划

  1. 确定dp数组以及下标的含义
    1. dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积
  2. 确定递推公式
    1. 将 i 拆分成 j 和 i - j 的和，且 i - j 不再拆分成多个正整数，此时的乘积是 j * ( i - j )；
    2. 将 i 拆分成 j 和 i - j 的和，且 i - j 继续拆分成多个正整数，此时的乘积是 j * dp[ i - j ]。
    3. 所以得到状态转移方程为：dp[i] = max( dp[i]，max( ( i - j ) j )，dp[i - j] j )；
  3. dp 的初始化
    1. 特别的，0不是正整数，1是最小的正整数，0和1都不能拆分，因此 dp[0] = dp[1] = 0；
    2. dp[2] = 1；
  4. 确定遍历顺序
    1. 确定遍历顺序，需要先看看递推公式：dp[i] = max( dp[i]，max( ( i - j ) j )，dp[i - j] j )；因为 dp[i] 是依靠 dp[i - 1]的状态，所以遍历 i 一定是从前往后遍历的，先有 dp[i - 1] 再有 dp[i]。
    2. 枚举 j 的时候是从 1 开始枚举的，i 是从 3 开始的，这样 dp[i - 1] 正好可以通过我们初始化的值求出来。
  5. 举例推导 dp 数组
    1. 举例当 n 为 10 的时候，dp 数组里的值如下：

image.png

C++完整代码如下：

  1. class Solution{
  2. public:
  3.     int integerBreak(int n) {
  4.         vector<int> dp(n + 1, 0);        // 默认初始化为0，但是最好还是显示定义
  5.         dp[2] = 1;
  6.         for(int i = 3; i <= n; i++){
  7.             for(int j = 1; j < i - 1; j++){
  8.                 dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  9.             }
  10.         }
  11.         return dp[n];
  12.     }
  13. };
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

贪心算法（二刷研究）

本题也可以用贪心，每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
我没有证明，而是直接用了结论。感兴趣的同学可以自己再去研究研究数学证明哈。
给出我的C++代码如下：

  1. class Solution {
  2. public:
  3.     int integerBreak(int n) {
  4.         if (n == 2) return 1;
  5.         if (n == 3) return 2;
  6.         if (n == 4) return 4;
  7.         int result = 1;
  8.         while (n > 4) {
  9.             result *= 3;
  10.             n -= 3;
  11.         }
  12.         result *= n;
  13.         return result;
  14.     }
  15. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

总结

本题掌握其动规的方法，就可以了，贪心的解法确实简单，但需要有数学证明，如果能自圆其说也是可以的。
其实这道题目的递推公式并不好想，而且初始化的地方也很有讲究，我在写本题的时候一开始写的代码是这样的：

  1. class Solution {
  2. public:
  3.     int integerBreak(int n) {
  4.         if (n <= 3) return 1 * (n - 1);
  5.         vector<int> dp(n + 1, 0);
  6.         dp[1] = 1;
  7.         dp[2] = 2;
  8.         dp[3] = 3;
  9.         for (int i = 4; i <= n ; i++) {
  10.             for (int j = 1; j < i - 1; j++) {
  11.                 dp[i] = max(dp[i], dp[i - j] * dp[j]);
  12.             }
  13.         }
  14.         return dp[n];
  15.     }
  16. };

这个代码也是可以过的！
在解释递推公式的时候，也可以解释通，dp[i] 就等于 拆解i - j的最大乘积 * 拆解j的最大乘积。 看起来没毛病！

但是在解释初始化的时候，就发现自相矛盾了，dp[1]为什么一定是1呢？根据dp[i]的定义，dp[2]也不应该是2啊。
但如果递归公式是 dp[i] = max(dp[i], dp[i - j] * dp[j]);，就一定要这么初始化。递推公式没毛病，但初始化解释不通！

虽然代码在初始位置有一个判断if (n <= 3) return 1 (n - 1);，保证n<=3 结果是正确的，但代码后面又要给dp[1]赋值1 和 dp[2] 赋值 2，*这其实就是自相矛盾的代码，违背了dp[i]的定义！

卡哥举这个例子，其实就说做题的严谨性，上面这个代码也可以AC，大体上一看好像也没有毛病，递推公式也说得过去，但是仅仅是恰巧过了而已。

9、不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）

image.png

思路

image.png
n为1的时候有一棵树，n为2有两棵树，这个是很直观的。
image.png
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] dp[0] + dp[1] dp[1] + dp[0] dp[2]

image.png

  1. 确定dp数组（dp table）以及下标的含义

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

  1. 确定递推公式

在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j - 1] dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

  1. dp数组如何初始化

初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
那么dp[0]应该是多少呢？
从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1

  1. 确定遍历顺序

首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
那么遍历i里面每一个数作为头结点的状态，用j来遍历。

  1. 举例推导dp数组

n为5时候的dp数组状态如图：
image.png
当然如果自己画图举例的话，基本举例到n为3就可以了，n为4的时候，画图已经比较麻烦了。
我这里列到了n为5的情况，是为了方便大家 debug代码的时候，把dp数组打出来，看看哪里有问题。
综上分析完毕，C++代码如下：

  1. class Solution{
  2. public:
  3.     int numTrees(int n){
  4.         vector<int> dp(n + 1, 0);
  5.         dp[0] = 1;
  6.         for(int i = 1; i <= n; i++){
  7.             for(int j = 1; j <= i; j++){
  8.                 dp[i] += dp[i - j] * dp[j - 1];
  9.             }
  10.         }
  11.         return dp[n];
  12.     }
  13. };
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

10、动规周总结

代码随想录 - 动态规划 - 10. 动规周总结

11、0-1背包理论基础（一）

背包问题的经典资料当然是：背包九讲。在公众号「代码随想录」后台回复：背包九讲，就可以获得背包九讲的pdf。
但说实话，背包九讲对于小白来说确实不太友好，看起来还是有点费劲的，而且都是伪代码理解起来也吃力。
对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。
如果这几种背包，分不清，我这里画了一个图，如下：
image.png

0-1背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
image.png
这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。
这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？
每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

举个例子：
背包最大重量为：4
物品为：


 重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

  1. 确定dp数组及下标的含义
    1. 对于背包问题，有一种写法，是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

只看这个二维数组的定义，大家一定会有点懵，看下面这个图：
image.png
要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。

  1. 确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]，

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：
image.png
在看其他情况。
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

代码初始化如下：

  1. for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
  2.     dp[0][j] = 0;
  3. }
  4. // 正序遍历
  5. for (int j = weight[0]; j <= bagweight; j++) {
  6.     dp[0][j] = value[0];
  7. }

此时dp数组初始化情况如图所示：
image.png
p[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？
其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
初始-1，初始-2，初始100，都可以！
但只不过一开始就统一把dp数组统一初始为0，更方便一些。
如图：
image.png

最后初始化代码如下：

  1. // 初始化 dp
  2. vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
  3. for (int j = weight[0]; j <= bagweight; j++) {
  4.     dp[0][j] = value[0];
  5. }

费了这么大的功夫，才把如何初始化讲清楚，相信不少同学平时初始化dp数组是凭感觉来的，但有时候感觉是不靠谱的。

  1. 确定遍历顺序

在如下图中，可以看出，有两个遍历的维度：物品与背包重量
image.png
那么问题来了，先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
那么我先给出先遍历物品，然后遍历背包重量的代码。

  1. // weight数组的大小 就是物品个数
  2. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  3.     for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  4.         if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
  5.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  7.     }
  8. }

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）
例如这样：

  1. // weight数组的大小 就是物品个数
  2. for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  3.     for(int i = 1; i < weight.size(); i++) { // 遍历物品
  4.         if (j < weight[i]) dp[i][j] = dp[i - 1][j];
  5.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  6.     }
  7. }

为什么也是可以的呢？
要理解递归的本质和递推的方向。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
image.png
再来看看先遍历背包，再遍历物品呢，如图：
image.png
大家可以看出，虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！
但先遍历物品再遍历背包这个顺序更好理解。
其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。

  1. 举例推导dp数组

来看一下对应的dp数组的数值，如图：
image.png
最终结果就是dp[2][4]。
建议大家此时自己在纸上推导一遍，看看dp数组里每一个数值是不是这样的。
做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！
很多同学做dp题目，遇到各种问题，然后凭感觉东改改西改改，怎么改都不对，或者稀里糊涂就改过了。
主要就是自己没有动手推导一下dp数组的演变过程，如果推导明白了，代码写出来就算有问题，只要把dp数组打印出来，对比一下和自己推导的有什么差异，很快就可以发现问题了。

完整C++代码如下：

  1. void test_2_wei_bag_problem1(){
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     int bagweight = 4;
  6.     // 二维数组
  7.     vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
  9.     // 初始化
  10.     for(int j = weight[0]; j <= bagweight; j++){
  11.         dp[0][j] = value[0];
  12.     }
  14.     // weight数组的大小就是物品的个数
  15.     for(int i = 1; i < weight.size(); i++){        // 遍历物品
  16.         for(int j = 0; j <= bagweight; j++){    // 遍历背包容量
  17.             if(j < weight[i]){
  18.                 dp[i][j] = dp[i - 1][j];
  19.             }
  20.             else{
  21.                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  22.             }
  23.         }
  24.     }
  26.     cout << dp[weight.size() - 1][begweight] << endl;
  27. }
  29. int main(){
  30.     test_2_wei_bag_problem1();
  31.     return 0;
  32. }

总结

讲了这么多才刚刚把二维dp的01背包讲完，这里大家其实可以发现最简单的是推导公式了，推导公式估计看一遍就记下来了，但难就难在如何初始化和遍历顺序上。
可能有的同学并没有注意到初始化 和 遍历顺序的重要性，我们后面做力扣上背包面试题目的时候，大家就会感受出来了。
下一篇 还是理论基础，我们再来讲一维dp数组实现的01背包（滚动数组），分析一下和二维有什么区别，在初始化和遍历顺序上又有什么差异，敬请期待！

12、0-1背包理论基础（二）

背包最大重量为4。
物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

一维dp数组（滚动数组）

使用二维数组的时候，递推公式：

  • dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现，我们依赖的 dp[i - 1][j] 正是 dp[i][j] 的上一层，这个表达式完全可以转换为：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。这就是滚动数组的由来。

使用滚动数组需要满足的条件：

  • 上一层可以重复利用，直接拷贝到当前层

之前 dp[i][j] 的定义：表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

动规五部曲分析如下：

  1. 确定dp数组的定义

    1. 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

  2. 一维dp数组的递推公式

    1. dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

  3. 一维dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？
看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。

  1. 一维dp数组遍历顺序
    1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
    2.  for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
    3.      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    4.  }
    5. }
    这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
为什么呢？

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
j
那么问题又来了，为什么二维dp数组历的时候不用倒序呢？
因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
（如何这里读不懂，大家就要动手试一试了，空想还是不靠谱的，实践出真知！）

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？
不可以！
因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
（这里如果读不懂，就在回想一下dp[j]的定义，或者就把两个for循环顺序颠倒一下试试！）

所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！，这一点大家一定要注意。

  1. 举例推导dp数组

一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下
image.png

一维dp01背包完整C++测试代码

  1. void test_1_wei_bag_problem() {
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     int bagWeight = 4;
  6.     // 初始化
  7.     vector<int> dp(bagWeight + 1, 0);
  8.     for(int i = 0; i < weight.size(); i++){                // 遍历物品
  9.         for(int j = bagWeight; j >= weight[i]; j--){    // 遍历背包    倒序遍历
  10.             dp[j] = max(dp[j], dp[j - weight[i] + value[i]);
  11.         }
  12.     }
  14.     cout << dp[bagWeight] << endl;
  15. }
  17. int main() {
  18.     test_1_wei_bag_problem();
  19.     return 0;
  20. }

13、分隔等和子集

416. 分割等和子集 - 力扣（LeetCode）

image.png

思路

背包问题有多种背包方式：0-1背包、完全背包、多重背包、分组背包、混合背包等等

要明确本题中我们使用的是 0-1 背包，因为每个元素我们只能用一次。

只有明确一下四点，才能把问题转化为 0-1 背包问题：

  1. 背包的容量为：sum / 2
  2. 背包要放入的商品（集合里的元素）重量为元素的值，价值也为元素的值
  3. 背包如果正好装满，说明找到了总和为 sum / 2 的集合
  4. 背包中每个元素是不可重复放入的。
  1. class Solution{
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         int sum = 0;
  5.         for(int i = 0; i < nums.size(); i++){
  6.             sum += nums[i];
  7.         }
  8.         if(sum % 2 == 1) return false;
  9.         int target = sum / 2;
  11.         // 由于是分成两个子集的元素和相等，所以背包问题只需要sum的一半
  12.         vector<int> dp(target + 1, 0);
  14.         // 开始 0-1 背包
  15.         for(int i = 0; i < nums.size(); i++){
  16.             for(int j = target; j >= nums[i]; j--){        // 每一个元素一定是不可重复放入，所以从大到小遍历
  17.                 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
  18.             }
  19.         }
  21.         // 容量为target的背包恰好等于target
  22.         if(dp[target] == target){
  23.             return true;
  24.         }
  25.         return false;
  26.     }
  27. };
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$，虽然dp数组大小为一个常数，但是大常数

总结
这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。
01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。
看代码的话，就可以发现，基本就是按照01背包的写法来的。

14、最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣（LeetCode）

image.png
image.png

思路

本题题意可以简练为：将数组 stones 中的元素两两做差后可能得到的最小值。

即我们应该尽可能的将数组 stones 分成 数值尽量相等的两等份，那么如何分成尽量相等的两等份呢？

  1. 计算整个数组的大小，然后除以2，即 target = sum / 2；
  2. 判断以 target 最为最大容量可能装载的 最大数值。即我们将问题转化成了 0-1 背包问题。
  3. sum - dp[target] - dp[target] 即为最小的可能重量

动规五部曲：

  1. dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
  2. 确定递归公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
  3. 初始化：应该将dp数组初始化为尽可能小的数，例如0（因为我们要求的是更大的数值）
  4. 遍历顺序：滚动数组：先遍历物品，再遍历背包，且背包是倒序遍历
  5. 举例推导 dp 数组
  1. class Solution {
  2. public:
  3.     int lastStoneWeightII(vector<int>& stones) {
  4.         int sum = 0;
  5.         for(int i = 0; i < stones.size(); i++){
  6.             sum += stones[i];
  7.         }
  8.         int target = sum / 2;
  10.         // dp[i] 取前i个石头的时候，可能取到的最大重量
  11.         vector<int> dp(target + 1, 0);      // 这里完全没有必要像卡哥那样写1501，这样太浪费空间了
  13.         for(int i = 0; i < stones.size(); i++){         // 遍历物品(石头)
  14.             for(int j = target; j >= stones[i]; j--){   // 遍历容量
  15.                 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
  16.             }
  17.         }
  18.         return sum - dp[target] - dp[target];
  19.     }
  20. };
  • 时间复杂度：$O(m × n)$ , m是石头总重量（准确的说是总重量的一半），n为石头块数
  • 空间复杂度：$O(m)$

15、动规周总结

代码随想录 - 动态规划 - 15. 动规周总结

16、目标和

494. 目标和

image.png
image.png

思路

对于给定的数组 nums，给上面的元素加 ‘+’ 或者 ‘-‘ ，使之运算结果等于 target，这样的表述，我们可以理解为：

  • -1 + 1 + 1 + 1 + 1 = 3；—> + 1 + 1 + 1 + 1 = 3 + 1；即让左右两个式子相等，就可以将问题转换为：
  • 我们要求一个目标值 Target = ( sum + target ) / 2；其中 sum 是 nums 数组的和

这样，我们就将问题转化成了类似于 回溯算法：39. 组合总和 的一道题目了

回溯法

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& nums, int target, int sum, int startIndex){
  6.         if(sum == target){
  7.             result.push_back(path);
  8.         }
  9.         for(int i = startIndex; i < nums.size() && sum + nums[i] <= target; i++){
  10.             path.push_back(nums[i]);
  11.             sum += nums[i];
  12.             backtracking(nums, target, sum, i + 1);
  13.             sum -= nums[i];
  14.             path.pop_back();
  15.         }
  16.     }
  17. public:
  18.     int findTargetSumWays(vector<int>& nums, int target) {
  19.         int sum = 0;
  20.         for(int i = 0; i < nums.size(); i++){
  21.             sum += nums[i];
  22.         }
  23.         if(target > sum) return 0;                // 此时没有方案
  24.         if((target + sum) % 2 == 1) return 0;    // 如果target和sum相差1，此时也肯定没有方案
  25.         int bagweight = (target + sum) / 2;        // 我们真正要求的目标值
  27.         // 以下是回溯代码
  28.         result.clear();
  29.         path.clear();
  30.         sort(nums.begin(), nums.end());            // 剪枝优化需要排序
  31.         backtracking(nums, bagweight, 0, 0);
  32.         return result.size();
  33.     }
  34. };

动态规划

可以将问题转化为 0-1 背包问题， target 是我们的背包容量，数组 nums 既是重量也是价值，但是本题与 0-1 背包略有不同的是，这道题求的是 不同表达式的数目，而不是最大价值，所以这道题本质还是在求组合问题。即我们的递推公式需要变更；

  1. 确定 dp 数组以及下标的含义

dp[i] 表示填满 i（包括i）这么大容积的包，有 dp[i] 种方法

  1. 确定递推公式
    • 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
    • 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
    • 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
    • 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
    • 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]
  2. dp 数组如何初始化
    • 从递归公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递归结果将都是0。
  3. 确定遍历顺序
  4. 推演

image.png

看文字不如看代码：
C++完整代码如下

  1. class Solution {
  2. public:
  3.     int findTargetSumWays(vector<int>& nums, int target) {
  4.         int sum = 0;
  5.         for(int i = 0; i < nums.size(); i++){
  6.             sum += nums[i];
  7.         }
  8.         if(target > sum) return 0;                // 此时没有方案
  9.         if((target + sum) % 2 == 1) return 0;    // 如果target和sum相差的值为奇数，此时也肯定没有方案
  10.         int bagweight = (target + sum) / 2;        // 背包容量
  12.         vector<int> dp(bagweight + 1, 0);
  13.         dp[0] = 1;                              // 如果容量为0，理应有1种方式
  14.         for(int i = 0; i < nums.size(); i++){               // 遍历物品
  15.             for(int j = bagweight; j >= nums[i]; j--){      // 后序遍历背包
  16.                 dp[j] += dp[j - nums[i]];
  17.             }
  18.         }
  19.         return dp[bagweight];
  20.     }
  21. };
  • 时间复杂度：$O(n × m)$，n为正数个数，m为背包容量
  • 空间复杂度：$O(m)$，m为背包容量

17、一和零

474. 一和零 - 力扣（LeetCode）

image.png

思路

首先，要确定这是什么问题？题目要我们求strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。那么如何求最大子集的长度？很明显，当前最大子集的长度，依赖于前一个最大子集的长度。所以可以确定这是一道动态规划题。

然后需要确定这是动态规划的哪种类型？由于数组 strs 中每个元素只能取一次，并且 m 和 n 其实就是背包的容量，是两个维度的背包，所以这是一道不折不扣的 0-1 背包问题。

动规五部曲：

  1. 确定 dp 数组及下标的定义

dp[i][j] 表示 有 i 个0 和 j 个 1 的时候，最大子集的长度

  1. 递归公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

  1. dp 数组的初始化

0-1 背包问题，数组的每个元素都不小于0，那么初始化为0就可以了

  1. 确定遍历顺序

在 0-1 背包的滚动数组中已经说过，滚动数组应该先遍历物品再遍历背包，且背包要从后往前遍历

  1. 手动推演

以输入：[“10”,”0001”,”111001”,”1”,”0”]，m = 3，n = 3为例
最后dp数组的状态如下所示：
image.png

C++完整代码如下：

  1. class Solution {
  2. public:
  3.     int findMaxForm(vector<string>& strs, int m, int n) {
  4.         // 初始化dp数组,默认初始化为0
  5.         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  6.         for(string s : strs){                   // 遍历物品
  7.             int zeroNum = 0, oneNum = 0;
  8.             for(int i = 0; i < s.size(); i++){
  9.                 if(s[i] == '0') zeroNum++;
  10.                 else oneNum++;
  11.             }
  12.             // 两个维度的容量
  13.             for(int i = m; i >= zeroNum; i--){  // 遍历背包，从后往前遍历
  14.                 for(int j = n; j >= oneNum; j--){
  15.                     dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
  16.                 }
  17.             }
  18.         }
  19.         return dp[m][n];
  20.     }
  21. };

18、完全背包理论基础

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中，我依然举这个例子：
背包最大重量为4。
物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个！
问背包能背的物品最大价值是多少？
01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！
关于01背包我如下两篇已经进行深入分析了：

首先在回顾一下01背包的核心代码

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

  1. // 先遍历物品，再遍历背包
  2. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  3.     for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
  4.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  6.     }
  7. }

至于为什么，我在动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)中也做了讲解。
dp状态图如下：
image.png
相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。
其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？
看过这两篇的话：

就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
image.png
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
image.png
看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。
先遍历被背包在遍历物品，代码如下：

  1. // 先遍历背包，再遍历物品
  2. for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
  3.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  4.         if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  5.     }
  6.     cout << endl;
  7. }


C++测试代码

完整的C++测试代码如下：

  1. void test_CompletePack() {
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     int bagWeight = 4;
  5.     vector<int> dp(bagWeight + 1, 0);
  6.     for(int i = 0; i < weight.size(); i++){                // 遍历物品
  7.         for(int j = weight[i]; j <= bagWeight; j++){    // 遍历背包容量
  8.             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  9.         }
  10.     }
  11.     cout << dp[bagWeight] << endl;
  12. }
  14. int main(){
  15.     test_CompletePack();
  16.     retrun 0;
  17. }
  1. void test_CompletePack() {
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     int bagWeight = 4;
  5.     vector<int> dp(bagWeight + 1, 0);
  6.     for(int j = 0; j <= bagWeight; j++){            // 遍历背包容量
  7.         for(int i = 0; j <= weight.size(); i++){    // 遍历物品
  8.             if(j >= weight[i]){
  9.                 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  10.             }
  11.         }
  12.     }
  13.     cout << dp[bagWeight] << endl;
  14. }
  16. int main(){
  17.     test_CompletePack();
  18.     retrun 0;
  19. }

总结

细心的同学可能发现，全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。
如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。
这个区别，我将在后面讲解具体leetcode题目中给大家介绍，因为这块如果不结合具题目，单纯的介绍原理估计很多同学会越看越懵！
别急，下一篇就是了！哈哈
最后，又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后在问，两个for循环的先后是否可以颠倒？为什么？ 这个简单的完全背包问题，估计就可以难住不少候选人了。

19、零钱兑换 II

518. 零钱兑换 II - 力扣（LeetCode）

image.png

思路

这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。

动规五部曲：

  1. 确定 dp 数组及下标的含义
    1. dp[j]：凑成总金额j的货币组合数为dp[j]
  2. 递推公式
    1. dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

所以递推公式：dp[j] += dp[j - coins[i]];
这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇动态规划：目标和！(opens new window)中就讲解了，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];

  1. 初始化 dp 数组
    1. 首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。

从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

  1. 遍历顺序（难点）
    1. 本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？

我在动态规划：关于完全背包，你该了解这些！(opens new window)中讲解了完全背包的两个for循环的先后顺序都是可以的。
但本题就不行了！
因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
而本题要求凑成总和的组合数，元素之间要求没有顺序。
所以纯完全背包是能凑成总和就行，不用管怎么凑的。
本题是求凑出来的方案个数，且每个方案个数是为组合数。
那么本题，两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

代码如下：

  1. for (int i = 0; i < coins.size(); i++) { // 遍历物品
  2.     for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
  3.         dp[j] += dp[j - coins[i]];
  4.     }
  5. }

假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：

  1. for (int j = 0; j <= amount; j++) { // 遍历背包容量
  2.     for (int i = 0; i < coins.size(); i++) { // 遍历物品
  3.         if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
  4.     }
  5. }

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

  1. 举例推导dp数组
  • 输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

image.png
最后红色框dp[amount]为最终结果。

以上分析完毕，C++代码如下：

  1. class Solution {
  2. public:
  3.     int change(int amount, vector<int>& coins) {
  4.         vector<int> dp(amount + 1, 0);
  5.         dp[0] = 1;
  6.         for(int i = 0; i < coins.size(); i++){          // 遍历硬币
  7.             for(int j = coins[i]; j <= amount; j++){    // 遍历背包容量,完全背包，从前往后遍历
  8.                 dp[j] += dp[j - coins[i]];
  9.             }
  10.         }
  11.         return dp[amount];
  12.     }
  13. };

总结

本题的递推公式，其实我们在动态规划：目标和！(opens new window)中就已经讲过了，而难点在于遍历顺序！
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
可能说到排列数录友们已经有点懵了，后面Carl还会安排求排列数的题目，到时候在对比一下，大家就会发现神奇所在！

20、动规周总结

377. 组合总和 Ⅳ - 力扣（LeetCode）

image.png
image.png

思路

  1. 数组 dp 的定义及其下标含义

dp[i] 表示目标整数为 i 的时候，nums 中返回总和为 i 的元素组合的个数

  1. 递推公式

dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。
因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。

  1. 初始化 dp 数组

因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
至于dp[0] = 1 有没有意义呢？
其实没有意义，所以我也不去强行解释它的意义了，因为题目中也说了：给定目标值是正整数！ 所以dp[0] = 1是没有意义的，仅仅是为了推导递推公式。
至于非0下标的dp[i]应该初始为多少呢？
初始化为0，这样才不会影响dp[i]累加所有的dp[i - nums[j]]。

  1. 遍历顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
（如果仍然不理解，建议手动画一画，一次不够画10次，铁壁能理解！）
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

  1. 手动推演

image.png

C++完整代码：

  1. class Solution {
  2. public:
  3.     int combinationSum4(vector<int>& nums, int target) {
  4.         vector<int> dp(target + 1, 0);
  5.         dp[0] = 1;      // 第0个理应由一种组合
  7.         // 因为题目的要求是找出sum==target的数组的全排列组合，
  8.         // 所以应该先遍历背包，再遍历物品
  9.         for(int j = 0; j <= target; j++){           // 先遍历背包
  10.             for(int i = 0; i < nums.size(); i++){   // 再遍历物品，且从前往后遍历
  11.                 // 需要注意的是，LC上的测试用例有INT型 overflow的，所以需要加判断(如果越界的地方正好是
  12.                 // 我们要求的target，那我觉得也无能为力！)
  13.                 if(j >= nums[i] && dp[j] <= INT_MAX - dp[j - nums[i]]){
  14.                     dp[j] += dp[j - nums[i]];
  15.                 }
  16.             }
  17.         }
  18.         return dp[target];
  19.     }
  20. };

22、爬楼梯（进阶版）

70. 爬楼梯 - 力扣（LeetCode）

image.png

1阶，2阶，…. m阶就是物品，楼顶就是背包。
且这道题是全排列

完整C++代码如下：

  1. class Solution {
  2. public:
  3.     int climbStairs(int n) {
  4.         vector<int> dp(n + 1, 0);
  5.         int m = 2;  // 因为每次可以爬1或2阶，m取每次可以爬的最大阶数
  6.         dp[0] = 1;  // 这里将dp[0]初始化为1其实没有什么实际的意义，为了解题方便
  7.         for(int i = 0; i <= n; i++){    // 遍历背包（n阶楼梯）
  8.             for(int j = 1; j <= m; j++){
  9.                 if(i >= j){
  10.                     dp[i] += dp[i - j];
  11.                 }
  12.             }
  13.         }
  14.         return dp[n];
  15.     }
  16. };

23、零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

image.png

思路

  1. 数组 dp 以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

  1. 确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

  1. dp 数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

  1. 确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在动态规划专题我们讲过了求组合数是动态规划：518.零钱兑换II(opens new window)，求排列数是动态规划：377. 组合总和 Ⅳ(opens new window)。
所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！
那么我采用coins放在外循环，target在内循环的方式。
本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序
综上所述，遍历顺序为：coins（物品）放在外循环，target（背包）在内循环。且内循环正序。

  1. 举例推导 dp 数组

image.png

C++完整代码：

  1. class Solution {
  2. public:
  3.     int coinChange(vector<int>& coins, int amount) {
  4.         vector<int> dp(amount + 1, INT_MAX);
  5.         dp[0] = 0;
  6.         for(int i = 1; i <= amount; i++){           // 先遍历背包
  7.             for(int j = 0; j < coins.size(); j++){  // 再遍历物品
  8.                 if(i >= coins[j] && dp[i - coins[j]] != INT_MAX){
  9.                     dp[i] = min(dp[i], dp[i - coins[j]] + 1);
  10.                 }
  11.             }
  12.         }
  13.         if(dp[amount] == INT_MAX) return -1;
  14.         return dp[amount];
  15.     }
  16. };

总结

细心的同学看网上的题解，可能看一篇是遍历背包的for循环放外面，看一篇又是遍历背包的for循环放里面，看多了都看晕了，到底两个for循环应该是什么先后关系。
能把遍历顺序讲明白的文章几乎找不到！
这也是大多数同学学习动态规划的苦恼所在，有的时候递推公式很简单，难在遍历顺序上！
但最终又可以稀里糊涂的把题目过了，也不知道为什么这样可以过，反正就是过了，哈哈
那么这篇文章就把遍历顺序分析的清清楚楚。
动态规划：518.零钱兑换II(opens new window)中求的是组合数，动态规划：377. 组合总和 Ⅳ(opens new window)中求的是排列数。
而本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！

24、完全平方数

279. 完全平方数 - 力扣（LeetCode）

image.png

思路

可能刚看这种题感觉没啥思路，又平方和的，又最小数的。
我来把题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
感受出来了没，这么浓厚的完全背包氛围，而且和昨天的题目动态规划：322. 零钱兑换(opens new window)就是一样一样的！

需要注意的是遍历顺序：
同样的，这道题求的是最小数，所以不管是组合还是排列都无所谓，反正我们只要最小数，所以先遍历背包再遍历物品或者先遍历物品再白能力背包都是可以的。

C++完整代码：

  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         // dp[i]：整数i的完全平方数的最少数量
  5.         vector<int> dp(n + 1, INT_MAX);
  6.         dp[0] = 0;  // 这里的dp[0]并没有什么实际意义，为了解题方便而初始化为0的
  7.         for(int i = 1; i <= n; i++){            // 遍历背包
  8.             for(int j = 1; j * j <= i; j++){    // 遍历物品
  9.                 dp[i] = min(dp[i], dp[i - j * j] + 1);
  10.             }
  11.         }
  12.         return dp[n];
  13.     }
  14. };
  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         // dp[i]：整数i的完全平方数的最少数量
  5.         vector<int> dp(n + 1, INT_MAX);
  6.         dp[0] = 0;  // 这里的dp[0]并没有什么实际意义，为了解题方便而初始化为0的
  7.         for(int j = 1; j * j <= n; j++){        // 遍历物品
  8.             for(int i = 1; i <= n; i++){        // 遍历背包
  9.                 if(i - j * j >= 0){
  10.                     dp[i] = min(dp[i], dp[i - j * j] + 1);
  11.                 }
  12.             }
  13.         }
  14.         return dp[n];
  15.     }
  16. };

25、动规周总结

代码随想录 - 动态规划 - 25. 动规周总结

26、单词拆分

139. 单词拆分 - 力扣（LeetCode）

image.png
image.png

思路

回溯问题

看到这道题目的时候，大家应该回想起我们之前讲解回溯法专题的时候，讲过的一道题目回溯算法：分割回文串(opens new window)，就是枚举字符串的所有分割情况。
回溯算法：分割回文串(opens new window)：是枚举分割后的所有子串，判断是否回文。
本道是枚举分割所有字符串，判断是否在字典里出现过。

那么这里我也给出回溯法C++代码：

  1. class Solution {
  2. private:
  3.     bool backtracking (const string& s, const unordered_set<string>& wordSet, int startIndex) {
  4.         if (startIndex >= s.size()) {
  5.             return true;
  6.         }
  7.         for (int i = startIndex; i < s.size(); i++) {
  8.             string word = s.substr(startIndex, i - startIndex + 1);
  9.             if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, i + 1)) {
  10.                 return true;
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. public:
  16.     bool wordBreak(string s, vector<string>& wordDict) {
  17.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
  18.         return backtracking(s, wordSet, 0);
  19.     }
  20. };
  • 时间复杂度：$O(2^n)$，因为每一个单词都有两个状态，切割和不切割
  • 空间复杂度：$O(n)$，算法递归系统调用栈的空间

递归的过程中有很多重复计算，可以使用数组保存一下递归过程中计算的结果。
这个叫做记忆化递归，这种方法我们之前已经提过很多次了。
使用memory数组保存每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果。
C++代码如下：

  1. class Solution {
  2. public:
  3.     bool backtracking(const string& s, const unordered_set<string>& wordSet, vector<int>& memory, int startIndex){
  4.         if(startIndex >= s.size()){
  5.             return true;
  6.         }
  8.         // 如果memory[startIndex] 不是初始值了，直接使用memory[startIndex]的结果
  9.         if(memory[startIndex] != -1) return memory[startIndex];
  10.         for(int i = startIndex; i < s.size(); i++){
  11.             string word = s.substr(startIndex, i - startIndex + 1);
  12.             if(wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)){
  13.                 memory[startIndex] = 1;     // 记录以startIndex开始的子串是可以被拆分的
  14.                 return true;
  15.             }
  16.         }
  17.         memory[startIndex] = 0;     // 记录以startIndex开始的子串是不可以被拆分的
  18.         return false;
  19.     }
  21.     bool wordBreak(string s, vector<string>& wordDict) {
  22.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
  23.         vector<int> memory(s.size(), -1);       // -1表示初始化状态
  24.         return backtracking(s, wordSet, memory, 0);
  25.     }
  26. };

背包问题

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！
动规五部曲分析如下：

  1. 确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

  1. 确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  1. dp数组如何初始化

从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。
那么dp[0]有没有意义呢？
dp[0]表示如果字符串为空的话，说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

  1. 确定遍历顺序

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
对这个结论还有疑问的同学可以看这篇本周小结！（动态规划系列五）(opens new window)，这篇本周小节中，我做了如下总结：
求组合数：动态规划：518.零钱兑换II(opens new window)求排列数：动态规划：377. 组合总和 Ⅳ(opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)求最小数：动态规划：322. 零钱兑换(opens new window)、动态规划：279.完全平方数(opens new window)
本题最终要求的是是否都出现过，所以对出现单词集合里的元素是组合还是排列，并不在意！
那么本题使用求排列的方式，还是求组合的方式都可以。
即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。
但本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环。
如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的子串都预先放在一个容器里。（如果不理解的话，可以自己尝试这么写一写就理解了）
所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。

  1. 举例推导dp[i]

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：
image.png
dp[s.size()]就是最终结果。
动规五部曲分析完毕，C++代码如下：

  1. class Solution {
  2. public:
  3.     bool wordBreak(string s, vector<string>& wordDict) {
  4.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
  5.         vector<bool> dp(s.size() + 1, false);
  6.         dp[0] = true;       // 为了解题而初始化
  8.         for(int i = 1; i <= s.size(); i++){     // 遍历背包
  9.             for(int j = 0; j < i; j++){         // 遍历物品
  10.                 string word = s.substr(j, i - j);      // substr(起始位置，截取区间)
  11.                 if(wordSet.find(word) != wordSet.end() && dp[j] == true){
  12.                     dp[i] = true;
  13.                 }
  14.             }
  15.         }
  16.         return dp[s.size()];
  17.     }
  18. };

27、多重背包理论知识

动态规划：关于多重背包，你该了解这些！

之前我们已经系统的讲解了01背包和完全背包，如果没有看过的录友，建议先把如下三篇文章仔细阅读一波。

这次我们再来说一说多重背包

#多重背包

对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
例如：
背包最大重量为10。
物品为：

重量 价值 数量
物品0 1 15 2
物品1 3 20 3
物品2 4 30 2

问背包能背的物品最大价值是多少？
和如下情况有区别么？

重量 价值 数量
物品0 1 15 1
物品0 1 15 1
物品1 3 20 1
物品1 3 20 1
物品1 3 20 1
物品2 4 30 1
物品2 4 30 1

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
这种方式来实现多重背包的代码如下：

  1. void test_multi_pack() {
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     vector<int> nums = {2, 3, 2};
  5.     int bagWeight = 10;
  6.     for (int i = 0; i < nums.size(); i++) {
  7.         while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
  8.             weight.push_back(weight[i]);
  9.             value.push_back(value[i]);
  10.             nums[i]--;
  11.         }
  12.     }
  14.     vector<int> dp(bagWeight + 1, 0);
  15.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  16.         for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  17.             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  18.         }
  19.         for (int j = 0; j <= bagWeight; j++) {
  20.             cout << dp[j] << " ";
  21.         }
  22.         cout << endl;
  23.     }
  24.     cout << dp[bagWeight] << endl;
  26. }
  27. int main() {
  28.     test_multi_pack();
  29. }
  • 时间复杂度：$O(m × n × k)$，m：物品种类个数，n背包容量，k单类物品数量

也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。

代码如下：（详看注释）

  1. void test_multi_pack() {
  2.     vector<int> weight = {1, 3, 4};
  3.     vector<int> value = {15, 20, 30};
  4.     vector<int> nums = {2, 3, 2};
  5.     int bagWeight = 10;
  6.     vector<int> dp(bagWeight + 1, 0);
  9.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  10.         for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  11.             // 以上为01背包，然后加一个遍历个数
  12.             for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
  13.                 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
  14.             }
  15.         }
  16.         // 打印一下dp数组
  17.         for (int j = 0; j <= bagWeight; j++) {
  18.             cout << dp[j] << " ";
  19.         }
  20.         cout << endl;
  21.     }
  22.     cout << dp[bagWeight] << endl;
  23. }
  24. int main() {
  25.     test_multi_pack();
  26. }
  • 时间复杂度：$O(m × n × k)$，m：物品种类个数，n背包容量，k单类物品数量

从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。
当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的包。
和以上在循环遍历上有所不同，因为是分拆为各个包最后可以组成一个完整背包，具体原理我就不做过多解释了，大家了解一下就行，面试的话基本不会考完这个深度了，感兴趣可以自己深入研究一波。

28、背包问题总结篇

听说背包问题很难？ 这篇总结篇来拯救你了
年前我们已经把背包问题都讲完了，那么现在我们要对背包问题进行总结一番。
背包问题是动态规划里的非常重要的一部分，所以我把背包问题单独总结一下，等动态规划专题更新完之后，我们还会在整体总结一波动态规划。

关于这几种常见的背包，其关系如下：
image.png
通过这个图，可以很清晰分清这几种常见背包之间的关系。
在讲解背包问题的时候，我们都是按照如下五部来逐步分析，相信大家也体会到，把这五部都搞透了，算是对动规来理解深入了。

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

其实这五部里哪一步都很关键，但确定递推公式和确定遍历顺序都具有规律性和代表性，所以下面我从这两点来对背包问题做一做总结。

背包递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

遍历顺序

01背包

在动态规划：关于01背包问题，你该了解这些！(opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
和动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

完全背包

说完01背包，再看看完全背包。
在动态规划：关于完全背包，你该了解这些！(opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
相关题目如下：

如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。

总结

这篇背包问题总结篇是对背包问题的高度概括，讲最关键的两部：递推公式和遍历顺序，结合力扣上的题目全都抽象出来了。
而且每一个点，我都给出了对应的力扣题目。
最后如果你想了解多重背包，可以看这篇动态规划：关于多重背包，你该了解这些！(opens new window)，力扣上还没有多重背包的题目，也不是面试考察的重点。
如果把我本篇总结出来的内容都掌握的话，可以说对背包问题理解的就很深刻了，用来对付面试中的背包问题绰绰有余！