29、打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

image.png

经典的递归五部曲

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

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

  1. 确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

  1. dp 数组如何初始化

    1. vector<int> dp(nums.size());
    2. dp[0] = nums[0];
    3. dp[1] = max(nums[0], nums[1]);

  2. 确定遍历顺序

很明显，dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

  1. 举例推演

image.png

C++完整代码如下：

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if(nums.size() == 0) return 0;
  5.         if(nums.size() == 1) return nums[0];
  7.         vector<int> dp(nums.size(), 0);     // dp[i]表示偷窃到第i间房屋时，最多偷盗的金额
  8.         dp[0] = nums[0];
  9.         dp[1] = max(dp[0], nums[1]);
  10.         for(int i = 2; i < nums.size(); i++){
  11.             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);    // 用dp[i - 1]模拟不偷的情况
  12.         }
  13.         return dp[nums.size() - 1];
  14.     }
  15. };

30、打家劫舍 II

213. 打家劫舍 II - 力扣（LeetCode）

image.png
image.png

思路

这道题目和198.打家劫舍(opens new window)是差不多的，唯一区别就是成环了。
对于一个数组，成环的话主要有如下三种情况：

  • 情况一：考虑不包含首尾元素

image.png

  • 情况二：考虑包含首元素，不包含尾元素

image.png

  • 情况三：考虑包含尾元素，不包含首元素

image.png
注意我这里用的是”考虑”，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
分析到这里，本题其实比较简单了。 剩下的和198.打家劫舍(opens new window)就是一样的了。

代码如下：

  1. // 注意注释中的情况二和情况三，以及把198.打家劫舍的代码抽离出来了
  2. class Solution{
  3. public:
  4.     int rob(vector<int>& nums) {
  5.         if(nums.size() == 0) return 0;
  6.         if(nums.size() == 1) return nums[0];
  7.         int result1 = robRange(nums, 0, nums.size() - 2);    // 情况二
  8.         int result2 = robRange(nums, 1, nums.size() - 1);    // 情况三
  9.         return max(result1, result2);
  10.     }
  12.     // 把198.打家劫舍的代码逻辑
  13.     int robRange(vector<int>& nums, int start, int end){
  14.         if(start == end) return nums[start];
  15.         vector<int> dp(nums.size(), 0);
  16.         dp[start] = nums[start];
  17.         dp[start + 1] = max(nums[start], nums[start + 1]);
  18.         for(int i = start + 2; i <= end; i++){
  19.             dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
  20.         }
  21.         return dp[end];
  22.     }
  23. };

总结

成环之后还是难了一些的， 不少题解没有把“考虑房间”和“偷房间”说清楚。
这就导致大家会有这样的困惑：情况三怎么就包含了情况一了呢？ 本文图中最后一间房不能偷啊，偷了一定不是最优结果。
所以我在本文重点强调了情况一二三是“考虑”的范围，而具体房间偷与不偷交给递推公式去抉择。
这样大家就不难理解情况二和情况三包含了情况一了。

31、打家劫舍 III

337. 打家劫舍 III - 力扣（LeetCode）

image.png
image.png

暴力递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int rob(TreeNode* root) {
  15.         if(root == nullptr) return 0;
  16.         if(root->left == nullptr && root->right == nullptr) return root->val;
  17.         // 偷取父节点
  18.         int val1 = root->val;
  19.         if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
  20.         if(root->right) val1 += rob(root->right->left) + rob(root->right->right);
  22.         // 不偷取父节点
  23.         int val2 = rob(root->left) + rob(root->right);
  25.         return max(val1, val2);
  26.     }
  27. };
  • 时间复杂度：$O(n^2)$，这个时间复杂度不太标准，也不容易准确化，例如越往下的节点重复计算次数就越多
  • 空间复杂度：$O(\log n)$，算上递推系统栈的空间

需要对这里的时间复杂度做一个理解说明：

  • 首先这一行代码：

    1. int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子

    假设数组长度为 n，那么二叉树的深度为 log(n)，所以单单这行代码的时间复杂度就为 O(2^log(n)) = O(n)

  • 其次

    1. if (root->left == NULL && root->right == NULL) return root->val;         
    2. if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回

    因为这两行代码是隔一层隔一层的遍历，所以起始它的时间复杂度等于上面时间复杂度的一半，即O(n/2)，因为是一个函数内的递归，所以时间复杂度为 O(n^1.5)，但随着二叉树的深度越深，1.5这个比重会越来越大（因为越下层的节点数越多），最终会逼近 O(n^2)。这就是为什么卡哥说 $O(n^2)$，这个时间复杂度不太标准，也不容易准确化，例如越往下的节点重复计算次数就越多

当然以上代码超时了，这个递归的过程中其实是有重复计算了。
我们计算了root的四个孙子（左右孩子的孩子）为头结点的子树的情况，又计算了root的左右孩子为头结点的子树的情况，计算左右孩子的时候其实又把孙子计算了一遍。因为不偷取父节点的计算，是一层一层的深度遍历，即 val2 通过计算每一层的结果然后与 val1 跳跃计算的每一层的结果进行比较，然后取其 max，看起来就像是递推公式很智能一样，但其实背后的计算量很大。

记忆化递推

所以可以使用一个map把计算过的结果保存一下，这样如果计算过孙子了，那么计算孩子的时候可以复用孙子节点的结果。
代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     unordered_map<TreeNode*, int> umap;     // 计算过的结果用 umap 保存起来
  15.     int rob(TreeNode* root) {
  16.         if(root == nullptr) return 0;
  17.         if(root->left == nullptr && root->right == nullptr) return root->val;
  18.         if(umap[root]) return umap[root];   // 如果 umap 有记录则直接返回
  19.         // 偷取父节点
  20.         int val1 = root->val;
  21.         if(root->left) val1 += rob(root->left->left) + rob(root->left->right);
  22.         if(root->right) val1 += rob(root->right->left) + rob(root->right->right);
  24.         // 不偷取父节点
  25.         int val2 = rob(root->left) + rob(root->right);      // 考虑root的左右孩子
  26.         umap[root] = max(val1, val2);       // umap记录一下结果
  28.         return max(val1, val2);
  29.     }
  30. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(\log n)$，算上递推系统栈的空间

动态规划

在上面两种方法，其实对一个节点 偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。
而动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。
这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

  1. 确定递归函数的参数和返回值

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
参数为当前节点，代码如下：

  1. vector<int> robTree(TreeNode* cur) {

其实这里的返回数组就是dp数组。
所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
所以本题dp数组就是一个长度为2的数组！
那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？
别忘了在递归的过程中，系统栈会保存每一层递归的参数。
如果还不理解的话，就接着往下看，看到代码就理解了哈。

  1. 确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

  1. if (cur == NULL) return vector<int>{0, 0};

这也相当于dp数组的初始化

  1. 确定遍历顺序

首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
通过递归左节点，得到左节点偷与不偷的金钱。
通过递归右节点，得到右节点偷与不偷的金钱。
代码如下：

  1. // 下标0：不偷，下标1：偷
  2. vector<int> left = robTree(cur->left); // 左
  3. vector<int> right = robTree(cur->right); // 右
  4. // 中
  1. 确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就在回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
代码如下：

  1. vector<int> left = robTree(cur->left); // 左
  2. vector<int> right = robTree(cur->right); // 右
  4. // 偷cur
  5. int val1 = cur->val + left[0] + right[0];
  6. // 不偷cur
  7. int val2 = max(left[0], left[1]) + max(right[0], right[1]);
  8. return {val2, val1};
  1. 举例推导dp数组

以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）
image.png
最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。
递归三部曲与动规五部曲分析完毕，C++代码如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int rob(TreeNode* root){
  15.         vector<int> result = robTree(root);
  16.         return max(result[0], result[1]);
  17.     }
  19.     // 长度为2的数组，0：不偷，1：偷
  20.     vector<int> robTree(TreeNode* cur){
  21.         if(cur == nullptr) return vector<int>{0, 0};
  22.         vector<int> left = robTree(cur->left);
  23.         vector<int> right = robTree(cur->right);
  24.         // 不偷的cur
  25.         int val0 = max(left[0], left[1]) + max(right[0], right[1]);
  26.         // 偷cur
  27.         int val1 = cur->val + left[0] + right[0];
  29.         return {val0, val1};
  30.     }
  31. };

32、买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

image.png

暴力

这道题目最直观的想法，就是暴力，找最优间距了。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices){
  4.         int result = 0;
  5.         for(int i = 0; i < prices.size(); i++){
  6.             for(int j = i + 1; j < prices.size(); j++){
  7.                 result = max(result, prices[j] - prices[i]);
  8.             }
  9.         }
  10.         return result;
  11.     }
  12. };

贪心

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int low = INT_MAX;
  5.         int result = 0;
  6.         for(int i = 0; i < prices.size(); i++){
  7.             low = min(low, prices[i]);              // 取最左最小价格
  8.             result = max(result, prices[i] - low);  // 取当前prices[i]与low的最大差值
  9.         }
  10.         return result;
  11.     }
  12. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

动态规划

  1. 数组 dp 及其下标含义

    • dp[i][0] 表示第i天不持有股票所得最多的现金
    • dp[i][1] 表示第i天持有股票所得最多的资金（这里是支付资金，所以是负数）

  2. 递推公式

    • dp[i][0] 可以由两个状态推出来

      • 如果第i-1天就不持有股票的话，那么就保持现状，所得现金就是昨天不持有股票所得的现金
      • 如果第i-1天持有股票的话，所得现金就是按照今天的股票价格卖出后所得现金 + i-1天支付的现金
        1. dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

    • dp[i][1] 可以由两个状态推出来

      • 如果第i-1天就持有股票了，那么久保持现状
      • 如果在第i天才持有股票，那么所得现第 i 天支付的现金
        1. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

  3. dp 如何初始化

  • 由递推公式可以看出，所有的计算都源自于 dp[0][0] 和 dp[0][1];
  1. 遍历顺序
  • 从前往后
  1. 举例推演

image.png

C++完整代码：

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         // dp[i][0] 表示第i天不持有股票需要支付的资金
  5.         // dp[i][1] 表示第i天持有股票所得最多现金
  6.         int len = prices.size();
  7.         if(len == 0) return 0;
  8.         vector<vector<int>> dp(len, vector<int>(2,0));
  9.         dp[0][0] = 0;           // 第i天不持有股票
  10.         dp[0][1] = -prices[0];  // 第i天持有股票
  11.         for(int i = 1; i < len; i++){
  12.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  13.             dp[i][1] = max(dp[i - 1][1], -prices[i]);
  14.         }
  15.         return max(dp[len - 1][0], dp[len - 1][1]);
  16.     }
  17. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

优化
从递推公式可以看出，dp[i]只是依赖于dp[i - 1]的状态。

  1. dp[i][0] = max(dp[i - 1][0], -prices[i]);
  2. dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了，可以使用滚动数组来节省空间，代码如下：

  1. // 版本二
  2. class Solution {
  3. public:
  4.     int maxProfit(vector<int>& prices) {
  5.         int len = prices.size();
  6.         vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
  7.         dp[0][0] -= prices[0];
  8.         dp[0][1] = 0;
  9.         for (int i = 1; i < len; i++) {
  10.             dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
  11.             dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
  12.         }
  13.         return dp[(len - 1) % 2][1];
  14.     }
  15. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

这里能写出版本一就可以了，版本二虽然原理都一样，但是想直接写出版本二还是有点麻烦，容易自己给自己找bug。
所以建议是先写出版本一，然后在版本一的基础上优化成版本二，而不是直接就写出版本二

33、动规周总结

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

34、买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II

image.png
image.png

思路

这道题同上面的 121. 买卖股票的最佳时机(opens new window) 是同样的思路，唯一的区别体现在递推公式上。
所以重点讲一讲递推公式
重申以下数组 dp 的含义

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

注意这里和121. 买卖股票的最佳时机(opens new window)唯一不同的地方，就是推导dp[i][0]的时候，第i天买入股票的情况。
在121. 买卖股票的最佳时机(opens new window)中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。
那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。

在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

注意这里和121. 买卖股票的最佳时机(opens new window)就是一样的逻辑，卖出股票收获利润（可能是负值）天经地义！

二维数组

代码如下：（注意代码中的注释，标记了和121.买卖股票的最佳时机唯一不同的地方）

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         // dp[i][0] 表示第i天不持有股票需要支付的资金
  5.         // dp[i][1] 表示第i天持有股票所得最多现金
  6.         int len = prices.size();
  7.         if(len == 0) return 0;
  8.         vector<vector<int>> dp(len, vector<int>(2, 0));
  9.         dp[0][0] = 0;           // 第i天不持有股票
  10.         dp[0][1] = -prices[0];  // 第i天吃有股票
  11.         for(int i = 1; i < dp.size(); i++){
  12.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  13.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
  14.         }
  15.         return max(dp[len - 1][0], dp[len - 1][1]);
  16.     }
  17. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

滚动数组

这道题仍然可以适用滚动数组来做，一刷的时候我就不重点看滚动数组了，二刷再来

这正是因为本题的股票可以买卖多次！ 所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。
想到到这一点，对这两道题理解的比较深刻了。
这里我依然给出滚动数组的版本，C++代码如下：

  1. // 版本二
  2. class Solution {
  3. public:
  4.     int maxProfit(vector<int>& prices) {
  5.         int len = prices.size();
  6.         vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
  7.         dp[0][0] -= prices[0];
  8.         dp[0][1] = 0;
  9.         for (int i = 1; i < len; i++) {
  10.             dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
  11.             dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
  12.         }
  13.         return dp[(len - 1) % 2][1];
  14.     }
  15. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

更轻巧的解法

这道题其实可以更简单，因为允许多次买卖股票，其实只需要转变一下思路，如果 【第i天 - 第i-1天】 的股票价格大于0，就说明有收益，那么我们便可以认为在 第i-1天买入，然后在第i天卖出，而不必去关系具体在哪一天买入在哪一天卖出。如果【第i天 - 第i-1天】不大于0，就不卖出。

C++完整代码如下：

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int result = 0;
  5.         for(int i = 1; i < prices.size(); i++){
  6.             result += max(prices[i] - prices[i - 1], 0);    
  7.         }
  8.         return result;
  9.     }
  10. };

35、买卖股票的最佳时机 III（困难）

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

image.png
image.png

思路

这道题目相对 121.买卖股票的最佳时机(opens new window)和 122.买卖股票的最佳时机II(opens new window)难了不少。
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
接来下我用动态规划五部曲详细分析一下：

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

一天一共就有五个状态，

  1. 没有操作
  2. 第一次买入
  3. 第一次卖出
  4. 第二次买入
  5. 第二次卖出

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

  1. 确定递推公式

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
达到dp[i][1]状态，有两个具体操作：

  • 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

  • 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分：
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

  1. dp数组如何初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，这个初始值应该是多少呢？
首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
所以dp[0][2] = 0;
第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
同理第二次卖出初始化dp[0][4] = 0;

  1. 确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

  1. 举例推导dp数组

以输入[1,2,3,4,5]为例
image.png
大家可以看到红色框为最后两次卖出的状态。
现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。
所以最终最大利润是dp[4][4]

以上五部都分析完了，不难写出如下代码：

  1. /*
  2.     动态规划:
  3.     确定 dp 数组的下标及其含义
  4.     一天共有5个状态：
  5.     0. 没有操作
  6.     1. 第一次买入
  7.     2. 第一次卖出
  8.     3. 第二次买入
  9.     4. 第二次卖出
  10. */
  12. class Solution {
  13. public:
  14.     int maxProfit(vector<int>& prices) {
  15.         if(prices.size() == 0) return 0;
  17.         // dp 数组初始化
  18.         vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
  19.         dp[0][0] = 0;           // 可以省略的，但是这样写体现出解题逻辑
  20.         dp[0][1] = -prices[0];
  21.         dp[0][2] = 0;           // 可以省略
  22.         dp[0][3] = -prices[0];
  23.         dp[0][4] = 0;           // 可以省略
  25.         for(int i = 1; i < prices.size(); i++){
  26.             dp[i][0] = dp[i - 1][0];                                    // 状态0
  27.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);     // 状态1
  28.             dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);     // 状态2
  29.             dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);     // 状态3
  30.             dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);     // 状态4
  31.         }
  32.         return dp[prices.size() - 1][4];        // 最大的收益一定是第二次交易
  33.     }
  34. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n × 5)$

当然，大家可以看到力扣官方题解里的一种优化空间写法，我这里给出对应的C++版本：

  1. // 版本二
  2. class Solution {
  3. public:
  4.     int maxProfit(vector<int>& prices) {
  5.         if (prices.size() == 0) return 0;
  6.         vector<int> dp(5, 0);
  7.         dp[1] = -prices[0];
  8.         dp[3] = -prices[0];
  9.         for (int i = 1; i < prices.size(); i++) {
  10.             dp[1] = max(dp[1], dp[0] - prices[i]);
  11.             dp[2] = max(dp[2], dp[1] + prices[i]);
  12.             dp[3] = max(dp[3], dp[2] - prices[i]);
  13.             dp[4] = max(dp[4], dp[3] + prices[i]);
  14.         }
  15.         return dp[4];
  16.     }
  17. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

大家会发现dp[2]利用的是当天的dp[1]。 但结果也是对的。
我来简单解释一下：
dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1]，即保持买入股票的状态，那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。
如果dp[1]取dp[0] - prices[i]，今天买入股票，那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是尽在再卖出股票，一买一卖收益为0，对所得现金没有影响。相当于今天买入股票又卖出股票，等于没有操作，保持昨天卖出股票的状态了。
这种写法看上去简单，其实思路很绕，不建议大家这么写，这么思考，很容易把自己绕进去！
对于本题，把版本一的写法研究明白，足以！

36、买卖股票的最佳时机 IV（困难）

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

image.png

思路

这道题的整体思路跟上面是一样的，唯一需要做判断的就是除了0之外，k % 2 == 1 就是买入，k % 2 == 0 就是卖出

C++完整代码如下：

  1. /*
  2.     k次交易一共又 2 * k + 1 种状态
  3.     0. 没有操作
  4.     1. 第一次买入
  5.     2. 第一次卖出
  6.     3. 第二次买入
  7.     4. 第二次卖出
  8.     5. 第三次买入
  9.     ...
  10.     2*k. 第 2*k 次卖出
  12. */
  13. class Solution {
  14. public:
  15.     int maxProfit(int k, vector<int>& prices) {
  16.         if(prices.size() == 0) return 0;
  17.         vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
  18.         // 初始化
  19.         for(int i = 0; i < 2 * k + 1; i++){
  20.             if(i % 2 == 1){     // 如果i % 2 == 1，说明是第ki次买入股票
  21.                 dp[0][i] = -prices[0];
  22.             }
  23.         }
  25.         for(int i = 1; i < prices.size(); i++){
  26.             dp[i][0] = dp[i - 1][0];
  27.             for(int j = 1; j <= 2 * k; j++){
  28.                 if(j % 2 == 1){
  29.                     dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
  30.                 }
  31.                 else{
  32.                     dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
  33.                 }
  35.             }
  36.         }
  38.         return dp[prices.size() - 1][2 * k];
  39.     }
  40. };

当然有的解法是定义一个三维数组dp[i][j][k]，第i天，第j次买卖，k表示买还是卖的状态，从定义上来讲是比较直观。
但感觉三维数组操作起来有些麻烦，我是直接用二维数组来模拟三维数组的情况，代码看起来也清爽一些。

37、最佳买卖股票时机含冷冻期

309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）

image.png

思路

相对于动态规划：122.买卖股票的最佳时机II(opens new window)，本题加上了一个冷冻期
在动态规划：122.买卖股票的最佳时机II(opens new window)中有两个状态，持有股票后的最多现金，和不持有股票的最多现金。
动规五部曲，分析如下：

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

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

其实本题很多同学搞的比较懵，是因为出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。 具体可以区分出如下四个状态：

  • 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
  • 卖出股票状态，这里就有两种卖出股票状态
    • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
    • 状态三：今天卖出了股票
  • 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

j的状态为：

  • 0：状态一
  • 1：状态二
  • 2：状态三
  • 3：状态四

很多题解为什么讲的比较模糊，是因为把这四个状态合并成三个状态了，其实就是把状态二和状态四合并在一起了。
从代码上来看确实可以合并，但从逻辑上分析合并之后就很难理解了，所以我下面的讲解是按照这四个状态来的，把每一个状态分析清楚。

注意这里的每一个状态，例如状态一，是买入股票状态并不是说今天已经就买入股票，而是说保存买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。

  1. 确定递推公式

达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

  • 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
  • 操作二：今天买入了，有两种情况
    • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
    • 前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]

所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

  • 操作一：前一天就是状态二
  • 操作二：前一天是冷冻期（状态四）

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

  • 操作一：昨天一定是买入股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

  • 操作一：昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

综上分析，递推代码如下：

  1. dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
  2. dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
  3. dp[i][2] = dp[i - 1][0] + prices[i];
  4. dp[i][3] = dp[i - 1][2];
  1. dp数组如何初始化

这里主要讨论一下第0天如何初始化。
如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。
保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，
今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。
同理dp[0][3]也初始为0。

  1. 确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

  1. 举例推导dp数组

以 [1,2,3,0,2] 为例，dp数组如下：
image.png
最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

代码如下：

  1. /*
  2.     状态一：买入股票状态（今天买入股票，或者是之前买入了股票然后没有操作）
  3.     卖出股票状态：
  4.         状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  5.         状态三：今天卖出了股票
  6.     状态四：今天为冷冻期，但冷冻期状态不可持续，只有一天！
  7. */
  8. class Solution{
  9. public:
  10.     int maxProfit(vector<int>& prices){
  11.         vector<vetcot<int> dp(prices.size(), vector<int>(4, 0));
  12.         dp[0][0] = -prices[0];        // 状态一
  13.         dp[0][1] = 0;                // 状态二
  14.         dp[0][2] = 0;                // 状态三
  15.         dp[0][3] = 0;                // 状态四
  16.         for(int i = 1; i < prices.size(); i++){
  17.             dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
  18.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
  19.             dp[i][2] = dp[i - 1][0] + prices[i];
  20.             dp[i][3] = dp[i - 1][2];
  21.         }
  22.         return max(dp[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));
  23.     }
  24. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

当然，空间复杂度可以优化，定义一个dp[2][4]大小的数组就可以了，就保存前一天的当前的状态，感兴趣的同学可以自己去写一写，思路是一样的。

这次把冷冻期这道题目，讲的很透彻了，细分为四个状态，其状态转移也十分清晰，建议大家都按照四个状态来分析，如果只划分三个状态确实很容易给自己绕进去。

38、动规周总结

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

39、买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

image.png
image.png

思路
相对于动态规划：122.买卖股票的最佳时机II(opens new window)，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。

动规五部曲：

  1. 数组 dp 及其下标的含义
  2. 确定递推公式
  3. 如何初始化 dp 数组
  4. 确定遍历顺序
  5. 推理演绎

这里只说数组 dp 的含义：

  • dp[i][0]：表示第i天没有购入股票 dp[i][0] = max(dp[i - 1][0], dp[i -1][1] + prices[i]);
  • dp[i][1]：表示第i天购入股票 dp[i][1] = max(dp[i - 1][1], dp[i -1][0] - prices[i]);

但是这道题每次交易都需要手续费，其实就是卖出的时候收取手续费，即
dp[i][0] = max(dp[i - 1][0], dp[i -1][1] + prices[i] - fee);

其余代码完全一样
C++完整代码如下：

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices, int fee) {
  4.         vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
  5.         dp[0][0] = 0;           // 第0天没有买入股票
  6.         dp[0][1] = -prices[0];  // 第0天买入了股票
  7.         for(int i = 1; i < prices.size(); i++){
  8.             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
  9.             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  10.         }
  11.         return max(dp[prices.size() - 1][1], dp[prices.size() - 1][0]);
  12.     }
  13. };
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

40、股票问题总结篇

代码随想录 - 动态规划 - 40、股票问题总结篇

41、最长上升子序列

300. 最长递增子序列 - 力扣（LeetCode）

image.png
image.png

最长上升子序列是动规的经典题目，这里dp[i]是可以根据dp[j] （j < i）推导出来的，那么依然用动规五部曲来分析详细一波：

  1. dp[i]的定义

dp[i]表示i之前包括i的最长上升子序列的长度。

  1. 状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

  1. dp[i]的初始化

每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是1.

  1. 确定遍历顺序

dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环在外层，遍历j则在内层，代码如下：

  1. for (int i = 1; i < nums.size(); i++) {
  2.     for (int j = 0; j < i; j++) {
  3.         if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  4.     }
  5.     if (dp[i] > result) result = dp[i]; // 取长的子序列
  6. }
  1. 举例推导dp数组

如果代码写出来，但一直AC不了，那么就把dp数组打印出来，看看对不对！
以上五部分析完毕，C++代码如下：

  1. class Solution {
  2. public:
  3.     int lengthOfLIS(vector<int>& nums) {
  4.         if(nums.size() <= 1) return nums.size();
  5.         // 数组dp及其下标含义为：dp[i]表示到第i个元素整数数组nums的最长子序列
  6.         vector<int> dp(nums.size(), 1);     // 只有一个数的最大子序列的长度应该是1
  7.         int result = 0;                     // 用result记录最大的dp[i]
  8.         for(int i = 1; i < nums.size(); i++){
  9.             for(int j = 0; j < i; j++){
  10.                 if(nums[i] > nums[j]){
  11.                     dp[i] = max(dp[i], dp[j] + 1);
  12.                 }
  13.             }
  14.             result = result > dp[i] ? result : dp[i];
  15.         }
  16.         return result;
  17.     }
  18. };

题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);
子序列问题是动态规划的一个重要系列，本题算是入门题目，好戏刚刚开始！

42、最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）

image.png

思路：

这道题比上面300. 最长递增子序列 - 力扣（LeetCode）这道题简单了很多，是因为这道题要求是连续的递增子序列，所以我们只需要对 nums[i] 和 nums[i - 1]，进行判断即可。

这里就不写动规五部曲了。

动态规划：

  1. class Solution {
  2. public:
  3.     int findLengthOfLCIS(vector<int>& nums) {
  4.         if(nums.size() <= 1) return nums.size();
  5.         vector<int> dp(nums.size(), 1);
  6.         int result = 0;     // 记录最长的连续递增子序列
  7.         for(int i = 1; i < nums.size(); i++){
  8.             if(nums[i] > nums[i - 1]){
  9.                 dp[i] = dp[i - 1] + 1;
  10.             }
  11.             result = result > dp[i] ? result : dp[i];
  12.         }
  13.         return result;
  14.     }
  15. };
  • 时间复杂度O(n)
  • 空间复杂度O(n)

当然这道题也可以适用贪心算法来求解

  1. class Solution {
  2. public:
  3.     int findLengthOfLCIS(vector<int>& nums) {
  4.         if(nums.size() <= 1) return nums.size();
  5.         int count = 1;      // 用来计算最长连续递增子序列的长度
  6.         int result = 0;     // 记录最长子序列
  7.         for(int i = 1; i < nums.size(); i++){
  8.             if(nums[i] > nums[i - 1]){
  9.                 count++;
  10.             }
  11.             else{
  12.                 count = 1;
  13.             }
  14.             result = result > count ? result : count;
  15.         }
  16.         return result;
  17.     }
  18. };
  • 时间复杂度O(n)
  • 空间复杂度O(1)

总结
本题也是动规里子序列问题的经典题目，但也可以用贪心来做，大家也会发现贪心好像更简单一点，而且空间复杂度仅是$O(1)$。
在动规分析中，关键是要理解和动态规划：300.最长递增子序列(opens new window)的区别。
要联动起来，才能理解递增子序列怎么求，递增连续子序列又要怎么求。
概括来说：不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关
本篇我也把区别所在之处重点介绍了，关键在递推公式和遍历方法上，大家可以仔细体会一波！

43、最长重复子数组

718. 最长重复子数组 - 力扣（LeetCode）

image.png

思路

注意题目中说的子数组，其实就是连续子序列。这种问题动规最拿手，动规五部曲分析如下：

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

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
此时细心的同学应该发现，那dp[0][0]是什么含义呢？总不能是以下标-1为结尾的A数组吧。
其实dp[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从1开始。
那有同学问了，我就定义dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？
行倒是行！ 但实现起来就麻烦一点，大家看下面的dp数组状态图就明白了。

  1. 确定递推公式

根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
根据递推公式可以看出，遍历i 和 j 要从1开始！

  1. dp数组如何初始化

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
举个例子A[0]如果和B[0]相同的话，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，正好符合递推公式逐步累加起来。

  1. 确定遍历顺序

外层for循环遍历A，内层for循环遍历B。
那又有同学问了，外层for循环遍历B，内层for循环遍历A。不行么？
也行，一样的，我这里就用外层for循环遍历A，内层for循环遍历B了。
同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i][j]的最大值记录下来。
代码如下：

  1. for (int i = 1; i <= A.size(); i++) {
  2.     for (int j = 1; j <= B.size(); j++) {
  3.         if (A[i - 1] == B[j - 1]) {
  4.             dp[i][j] = dp[i - 1][j - 1] + 1;
  5.         }
  6.         if (dp[i][j] > result) result = dp[i][j];
  7.     }
  8. }
  1. 举例推导dp数组

拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：
image.png

二维数组

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

  1. class Solution {
  2. public:
  3.     int findLength(vector<int>& nums1, vector<int>& nums2){
  4.         vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
  5.         int result = 0;
  6.         for(int i = 1; i <= nums1.size(); i++){
  7.             for(int j = 1; j <= nums2.size(); j++){
  8.                 if(nums1[i - 1] == nums2[j - 1]){
  9.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  10.                 }
  11.                 result = result > dp[i][j] ? result : dp[i][j];
  12.             }
  13.         }
  14.         return result;
  15.     }
  16. };

滚动数组

在如下图中：
image.png
我们可以看出dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组，也就是dp[j]都是由dp[j - 1]推出。
也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。

此时遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。

  1. class Solution {
  2. public:
  3.     int findLength(vector<int>& A, vector<int>& B) {
  4.         vector<int> dp(vector<int>(B.size() + 1, 0));
  5.         int result = 0;
  6.         for (int i = 1; i <= A.size(); i++) {
  7.             for (int j = B.size(); j > 0; j--) {
  8.                 if (A[i - 1] == B[j - 1]) {
  9.                     dp[j] = dp[j - 1] + 1;
  10.                 } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作
  11.                 if (dp[j] > result) result = dp[j];
  12.             }
  13.         }
  14.         return result;
  15.     }
  16. };

44、最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

image.png
image.png

思路

本题和动态规划：718. 最长重复子数组(opens new window)区别在于这里不要求是连续的了，但要有相对顺序，即：”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
不是连续意味着，我们如果当前 text1[i] != text2[i] ，这个时候需要保存上次的最大值，即 dp[i][j] = max( dp[i - 1][j]，dp[i][j - 1] )；

其余的动规五部曲都是一样的。
需要注意的是，这道题的遍历顺序是从前往后遍历，先遍历text1 或者是 text2 都是一样的。

  1. class Solution {
  2. public:
  3.     int longestCommonSubsequence(string text1, string text2) {
  4.         int len1 = text1.size();
  5.         int len2 = text2.size();
  6.         if(len1 == 0 || len2 == 0) return 0;
  7.         vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
  8.         int result = 0;
  9.         for(int i = 1; i <= len1; i++){
  10.             for(int j = 1; j <= len2; j++){
  11.                 if(text1[i - 1] == text2[j - 1]){
  12.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  13.                 }
  14.                 else{
  15.                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  16.                 }
  17.             }
  18.         }
  19.         return dp[len1][len2];
  20.     }
  21. };

45、不相交的线

1035. 不相交的线 - 力扣（LeetCode）

image.png
image.png

思路

相信不少录友看到这道题目都没啥思路，我们来逐步分析一下。
绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：
image.png

其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）
这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
那么本题就和我们刚刚讲过的这道题目动态规划：1143.最长公共子序列(opens new window)就是一样一样的了。
一样到什么程度呢？ 把字符串名字改一下，其他代码都不用改，直接copy过来就行了。
其实本题就是求最长公共子序列的长度，介于我们刚刚讲过动态规划：1143.最长公共子序列(opens new window)，所以本题我就不再做动规五部曲分析了。
如果大家有点遗忘了最长公共子序列，就再看一下这篇：动态规划：1143.最长公共子序列(opens new window)

本题代码如下：

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

46、最大子序和

53. 最大子数组和 - 力扣（LeetCode）

image.png

思路

这道题之前我们在讲解贪心专题的时候用贪心算法解决过一次，贪心算法：最大子序和(opens new window)。
这次我们用动态规划的思路再来分析一次。
动规五部曲如下：

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

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

  1. 确定递推公式

dp[i]只有两个方向可以推出来：

  • dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
  • nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

  1. dp数组如何初始化

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
dp[0]应该是多少呢?
根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。

  1. 确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

  1. 举例推导dp数组

以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下： image.png
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。
在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候，可以直接选出最大的dp[i]。

以上动规五部曲分析完毕，完整代码如下：

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

47、判断子序列

392. 判断子序列 - 力扣（LeetCode）

image.png

思路

（这道题可以用双指针的思路来实现，时间复杂度就是$O(n)$）
这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。
所以掌握本题也是对后面要讲解的编辑距离的题目打下基础。
动态规划五部曲分析如下：

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

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
有同学问了，为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？
用i来表示也可以！
但我统一以下标i-1为结尾的字符串来计算，这样在下面的递归公式中会容易理解一些，如果还有疑惑，可以继续往下看。

  1. 确定递推公式

在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

  • if (s[i - 1] == t[j - 1])
    • t中找到了一个字符在s中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于t要删除元素，继续匹配

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）
if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

  1. dp数组如何初始化

从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。
这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：
image.png
如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。
这里dp[i][0]和dp[0][j]是没有含义的，仅仅是为了给递推公式做前期铺垫，所以初始化为0。
其实这里只初始化dp[i][0]就够了，但一起初始化也方便，所以就一起操作了，代码如下：

  1. vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
  1. 确定遍历顺序

同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右
如图所示：
image.png

  1. 举例推导dp数组

以示例一为例，输入：s = “abc”, t = “ahbgdc”，dp状态转移图如下：
image.png
dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。
图中dp[s.size()][t.size()] = 3， 而s.size() 也为3。所以s是t 的子序列，返回true。

动规五部曲分析完毕，C++代码如下：

  1. class Solution {
  2. public:
  3.     bool isSubsequence(string s, string t) {
  4.         if(s.size() > t.size()) return false;
  5.         // 这里定义dp数组的时候，也把分析dp数组初始化的工作一起做了（因为dp[0][0]和dp[i][0]都要初始化为0）
  6.         vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
  7.         for(int i = 1; i <= s.size(); i++){
  8.             for(int j = 1; j <= t.size(); j++){
  9.                 if(s[i - 1] == t[j - 1]){
  10.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  11.                 }
  12.                 else{
  13.                     dp[i][j] = dp[i][j - 1];
  14.                 }
  15.             }
  16.         }
  17.         if(dp[s.size()][t.size()] == s.size()){
  18.             return true;
  19.         }
  20.         return false;
  21.     }
  22. };

48、不同子序列

115. 不同的子序列 - 力扣（LeetCode）

image.png
image.png

思路
这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用KMP。
这道题目相对于72. 编辑距离，简单了不少，因为本题相当于只有删除操作，不用考虑替换增加之类的。
但相对于刚讲过的动态规划：392.判断子序列(opens new window)就有难度了，这道题目双指针法可就做不了了，来看看动规五部曲分析如下：

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

dp[i][j]：以 i-1 为结尾的s子序列中出现以 j-1 为结尾的t的个数为dp[i][j]。

  1. 确定递推公式

这一类问题，基本是要分析两种情况

  • s[i - 1] 与 t[j - 1]相等
  • s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

这里可能有同学不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。
例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

如果吧 s：bagg 和 t：bag 的例子不够形象，那么试试手动写一写 s：badg 和 t：bag，这样就能够理解了。

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]
所以递推公式为：dp[i][j] = dp[i - 1][j];

  1. dp数组如何初始化

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][0] 和dp[0][j]是一定要初始化的。
每次当初始化的时候，都要回顾一下dp[i][j]的定义，不要凭感觉初始化。
dp[i][0]表示什么呢？
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
再来看dp[0][j]，dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
那么dp[0][j]一定都是0，s如论如何也变成不了t。
最后就要看一个特殊位置了，即：dp[0][0] 应该是多少。
dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
初始化分析完毕，代码如下：

  1. vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
  2. for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
  3. for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其实这行代码可以和dp数组初始化的时候放在一起，但我为了凸显初始化的逻辑，所以还是加上了。
  1. 确定遍历顺序

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。
所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
代码如下：

  1. for (int i = 1; i <= s.size(); i++) {
  2.     for (int j = 1; j <= t.size(); j++) {
  3.         if (s[i - 1] == t[j - 1]) {
  4.             dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  5.         } else {
  6.             dp[i][j] = dp[i - 1][j];
  7.         }
  8.     }
  9. }
  1. 举例推导dp数组

动规五部曲分析完毕，代码如下：

  1. class Solution {
  2. public:
  3.     int numDistinct(string s, string t) {
  4.         vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
  5.         for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
  6.         for (int j = 0; j < t.size(); j++) dp[0][j] = 0;
  7.         dp[0][0] = 1;
  8.         for (int i = 1; i <= s.size(); i++) {
  9.             for (int j = 1; j <= t.size(); j++) {
  10.                 if(s[i - 1] == t[j - 1]){
  11.                     dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  12.                 }
  13.                 else{
  14.                     dp[i][j] = dp[i - 1][j];
  15.                 }
  16.             }
  17.         }
  18.         return dp[s.size()][t.size()];
  19.     }
  20. };

49、两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode)

image.png

思路

动态规划一

本题和动态规划：115.不同的子序列(opens new window)相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。
这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

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

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
这里dp数组的定义有点点绕，大家要撸清思路。

  1. 确定递推公式
  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

注意：因为 dp[i - 1][j - 1] + 2 删除两个数的情况肯定比只删除一个数糟糕，在实际中，肯定遇到一个不符合的字符就删掉一个，不会是两个同时删掉的，在这里我们为了让代码更加具有逻辑性，所以保留了这种情况。

  1. dp数组如何初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。
dp[0][j]的话同理，所以代码如下：

  1. vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
  2. for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
  3. for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
  1. 确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。
所以遍历的时候一定是从上到下，从左到右，这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

  1. 举例推导dp数组

以word1:”sea”，word2:”eat”为例，推导dp数组状态图如下：
image.png
以上分析完毕，代码如下：

  1. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
  5.         for(int i = 0; i <= word1.size(); i++) dp[i][0] = i;
  6.         for(int j = 0; j <= word2.size(); j++) dp[0][j] = j;
  7.         for(int i = 1; i <= word1.size(); i++){
  8.             for(int j = 1; j <= word2.size(); j++){
  9.                 if(word1[i - 1] == word2[j - 1]){
  10.                     dp[i][j] = dp[i - 1][j - 1];
  11.                 }
  12.                 else{
  13.                     dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
  14.                 }
  15.             }
  16.         }
  17.         return dp[word1.size()][word2.size()];
  18.     }
  19. };

动态规划二

本题和动态规划：1143.最长公共子序列(opens new window)基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

  1. class Solution {
  2. public:
  3.     // 转化为最长公共子串问题
  4.     int minDistance(string word1, string word2) {
  5.         vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
  6.         for(int i = 1; i <= word1.size(); i++){
  7.             for(int j = 1; j <= word2.size(); j++){
  8.                 if(word1[i - 1] == word2[j - 1]){       // 记录最长公共子串的长度
  9.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  10.                 }
  11.                 else{
  12.                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  13.                 }
  14.             }
  15.         }
  16.         return word1.size() + word2.size() - dp[word1.size()][word2.size()] * 2;
  17.     }
  18. };

50、编辑距离（困难）

72. 编辑距离 - 力扣（LeetCode）

image.png
image.png

思路

编辑距离终于来了，这道题目如果大家没有了解动态规划的话，会感觉超级复杂。
编辑距离是用动规来解决的经典题目，这道题目看上去好像很复杂，但用动规可以很巧妙的算出最少编辑距离。
接下来我依然使用动规五部曲，对本题做一个详细的分析：

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

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
这里在强调一下：为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？
用i来表示也可以！ 但我统一以下标i-1为结尾的字符串，在下面的递归公式中会容易理解一点。

2. 确定递推公式

在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

  1. if (word1[i - 1] == word2[j - 1])
  2.     不操作
  3. if (word1[i - 1] != word2[j - 1])
  4.     增
  5.     删
  6.     换

也就是如上4种情况。
if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
此时可能有同学有点不明白，为啥要即dp[i][j] = dp[i - 1][j - 1]呢？

那么就在回顾上面讲过的dp[i][j]的定义，word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。
在下面的讲解中，如果哪里看不懂，就回想一下dp[i][j]的定义，就明白了。

在整个动规的过程中，最为关键就是正确理解dp[i][j]的定义！
if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

  • 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i - 1][j] + 1;

  • 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是删除元素，添加元素去哪了。
word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=”a”, word2=”ad”， 最终的操作数是一样！ dp数组如下图所示意的：

  1.             a                         a     d
  2.    +-----+-----+             +-----+-----+-----+
  3.    |  0  |  1  |             |  0  |  1  |  2  |
  4.    +-----+-----+   ===>      +-----+-----+-----+
  5.  a |  1  |  0  |           a |  1  |  0  |  1  |
  6.    +-----+-----+             +-----+-----+-----+
  7.  d |  2  |  1  |
  8.    +-----+-----+

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。
即 dp[i][j] = dp[i - 1][j - 1] + 1;
综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
递归公式代码如下:

  1. if (word1[i - 1] == word2[j - 1]) {
  2.     dp[i][j] = dp[i - 1][j - 1];
  3. }
  4. else {
  5.     dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
  6. }

3. dp数组如何初始化

再回顾一下dp[i][j]的定义：
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

那么dp[i][0] 和 dp[0][j] 表示什么呢？
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;
同理dp[0][j] = j;
所以C++代码如下：

  1. for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
  2. for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

4. 确定遍历顺序

从如下四个递推公式：

  • dp[i][j] = dp[i - 1][j - 1]
  • dp[i][j] = dp[i - 1][j - 1] + 1
  • dp[i][j] = dp[i][j - 1] + 1
  • dp[i][j] = dp[i - 1][j] + 1

可以看出dp[i][j]是依赖左方，上方和左上方元素的，如图：

image.png

所以在dp矩阵中一定是从左到右从上到下去遍历。
代码如下：

  1. for (int i = 1; i <= word1.size(); i++) {
  2.     for (int j = 1; j <= word2.size(); j++) {
  3.         if (word1[i - 1] == word2[j - 1]) {
  4.             dp[i][j] = dp[i - 1][j - 1];
  5.         }
  6.         else {
  7.             dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
  8.         }
  9.     }
  10. }

5. 举例推导dp数组

以上动规五部分析完毕，C++代码如下：

  1. /*
  2.     1. dp数组及其下标定义：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最少编辑距离为dp[i][j]。
  3.     2. 分为4种情况
  4.         2.1：不操作   --> dp[i][j] = dp[i - 1][j - 1];
  5.         2.2：增       --> dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
  6.         2.3：删       --> 删除一个字母相当于在另一个字符串增加一个字母
  7.         2.3: 替       --> dp[i][j] = dp[i - 1][j - 1] + 1;
  8. */
  11. class Solution {
  12. public:
  13.     int minDistance(string word1, string word2) {
  14.         vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
  15.         for(int i = 1; i <= word1.size(); i++) dp[i][0] = i;
  16.         for(int j = 1; j <= word2.size(); j++) dp[0][j] = j;
  17.         dp[0][0] = 0;
  18.         for(int i = 1; i <= word1.size(); i++){
  19.             for(int j = 1; j <= word2.size(); j++){
  20.                 if(word1[i - 1] == word2[j - 1]){
  21.                     dp[i][j] = dp[i - 1][j - 1];
  22.                 }
  23.                 else{
  24.                     dp[i][j] = min({dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
  25.                 }
  26.             }
  27.         }
  28.         return dp[word1.size()][word2.size()];
  29.     }
  30. };

51、编辑距离总结篇

代码随想录 - 动态规划 - 51、编辑距离总结篇

52、回文子串

647. 回文子串 - 力扣（LeetCode）

image.png

思路

暴力解法

两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。
时间复杂度：$O(n^3)$

动态规划

动规五部曲：

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

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

  1. 确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差不大于2，例如 aa 或 aba，也是文子串
  • 情况三：下标：i 与 j相差大于2的时候，例如 cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

以上三种情况分析完了，那么递归公式如下：

  1. if (s[i] == s[j]) {
  2.     if (j - i <= 2) { // 情况一 和 情况二
  3.         result++;
  4.         dp[i][j] = true;
  5.     } else if (dp[i + 1][j - 1]) { // 情况三
  6.         result++;
  7.         dp[i][j] = true;
  8.     }
  9. }

result就是统计回文子串的数量。
注意这里我没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i][j]初始化的时候，就初始为false。

  1. dp数组如何初始化

dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
所以dp[i][j]初始化为false。

  1. 确定遍历顺序

遍历顺序可有有点讲究了。
首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。
dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：
image.png

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。
代码如下：

  1. for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
  2.     for (int j = i; j < s.size(); j++) {
  3.         if (s[i] == s[j]) {
  4.             if (j - i <= 2) { // 情况一 和 情况二
  5.                 result++;
  6.                 dp[i][j] = true;
  7.             } else if (dp[i + 1][j - 1]) { // 情况三
  8.                 result++;
  9.                 dp[i][j] = true;
  10.             }
  11.         }
  12.     }
  13. }
  1. 举例推导dp数组

举例，输入：”aaa”，dp[i][j]状态如下：
image.png

图中有6个true，所以就是有6个回文子串。
注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

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

  1. /*
  2.     推出递推公式有三种情况：
  3.         情况1：下标 i 与 j 相同，同一个字符，例如 a，当然是回文串
  4.         情况2：下标 i 与 j 相差不大于2，例如 aa 或 aba，也是回文串
  5.         情况3：下标 i 与 j 相差大于2，例如 cabac，此时 s[i] 与 s[j] 已经相同了，我们看 i 到 j 区间是不是回文子串
  6.                 就看 abc 是不是回文就可以了，那么 abc 的区间就是 i + 1 与 j - 1 区间，这个区间是不是回文就看 dp[i + 1][j - 1] 是否为true
  7. */
  9. class Solution {
  10. public:
  11.     int countSubstrings(string s) {
  12.         // 表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false
  13.         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  14.         int result = 0;                         // 计算结果
  15.         // 因为递推公式：dp[i][j] 依赖于 dp[i + 1][j - 1]，所以遍历顺序要 从下到上，从左到右遍历
  16.         for(int i = s.size() - 1; i >= 0; i--){        // 从下到上
  17.             for(int j = i; j < s.size(); j++){        // 从左到右
  18.                 if(s[i] == s[j]){
  19.                     if(j - i <= 2){             // 情况1和情况2
  20.                         dp[i][j] = true;
  21.                         result++;
  22.                     }
  23.                     else if(dp[i + 1][j - 1]){  // 情况3
  24.                         dp[i][j] = true;
  25.                         result++;
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         return result;
  31.     }
  32. };

53、最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

image.png

思路

整体思路继承上面的 647. 回文子串 （计算回文子串的个数），但是这道题需要返回的是字符串，所以需要额外做一些操作。

C++完整代码：

  1. /*
  2.     推出递推公式有三种情况：
  3.         情况1：下标 i 与 j 相同，同一个字符，例如 a，当然是回文串
  4.         情况2：下标 i 与 j 相差不大于2，例如 aa 或 aba，也是回文串
  5.         情况3：下标 i 与 j 相差大于2，例如 cabac，此时 s[i] 与 s[j] 已经相同了，我们看 i 到 j 区间是不是回文子串
  6.                 就看 abc 是不是回文就可以了，那么 abc 的区间就是 i + 1 与 j - 1 区间，这个区间是不是回文就看 dp[i + 1][j - 1] 是否为true
  7. */
  9. class Solution {
  10. public:
  11.     string longestPalindrome(string s) {
  12.         if(s.size() <= 1) return s;
  13.         // 表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false
  14.         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  15.         string str = "";
  16.         int begin = 0;      // 回文子串开始的索引
  17.         int maxLen = 1;     // 回文子串的最大长度，因为一个字符一定是回文串，所以初始化为1
  18.         int curLen = 0;     // 当前回文子串的长度
  19.         bool flag = false;  // 判断字符串s是否存在回文子串
  20.         // 因为递推公式：dp[i][j] 依赖于 dp[i + 1][j - 1]，所以遍历顺序要 从下到上，从左到右遍历
  21.         for(int i = s.size() - 1; i >= 0; i--){
  22.             for(int j = i + 1; j < s.size(); j++){
  23.                 if(s[i] == s[j]){
  24.                     if(j - i <= 2){         // 情况1和情况2
  25.                         dp[i][j] = true;
  26.                         curLen = j - i + 1;
  27.                     }
  28.                     else if(dp[i + 1][j - 1]){
  29.                         dp[i][j] = true;
  30.                         curLen = j - i + 1;
  31.                     }
  32.                 }
  33.                 if(dp[i][j] == true && curLen > maxLen){
  34.                     begin = i;
  35.                     maxLen = curLen;
  36.                     flag = true;
  37.                 }
  38.             }
  39.         }
  40.         if(flag == false) return s.substr(0, 1);
  41.         return s.substr(begin, maxLen);
  42.     }
  43. };

54、最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

image.png

思路

我们刚刚做过了 动态规划：回文子串(opens new window)，求的是回文子串，而本题要求的是回文子序列， 要搞清楚这两者之间的区别。
回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目。
回文子串，可以做这两题：

  • 647.回文子串
  • 5.最长回文子串

思路其实是差不多的，但本题要比求回文子串简单一点，因为情况少了一点。

动规五部曲分析如下：

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

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

  1. 确定递推公式

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;
如图： image.png
（如果这里看不懂，回忆一下dp[i][j]的定义）
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。
那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
image.png
代码如下：

  1. if (s[i] == s[j]) {
  2.     dp[i][j] = dp[i + 1][j - 1] + 2;
  3. } else {
  4.     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  5. }
  1. dp数组如何初始化

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

  1. vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
  2. for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
  1. 确定遍历顺序

从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，
也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。
递推公式：dp[i][j] = dp[i + 1][j - 1] + 2，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 分别对应着下图中的红色箭头方向，如图：
image.png
代码如下：

  1. for (int i = s.size() - 1; i >= 0; i--) {
  2.     for (int j = i + 1; j < s.size(); j++) {
  3.         if (s[i] == s[j]) {
  4.             dp[i][j] = dp[i + 1][j - 1] + 2;
  5.         } else {
  6.             dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  7.         }
  8.     }
  9. }
  1. 举例推导dp数组

输入s:”cbbd” 为例，dp数组状态如图：
image.png

红色框即：dp[0][s.size() - 1]; 为最终结果。
以上分析完毕，C++代码如下：

  1. class Solution {
  2. public:
  3.     int longestPalindromeSubseq(string s) {
  4.         // dp[i]表示边界为i到j区间的字符串对应的最长的回文子序列的长度
  5.         vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
  6.         // 初始化
  7.         for(int i = 0; i < s.size(); i++){
  8.             dp[i][i] = 1;
  9.         }
  10.         // 因为递推公式：dp[i][j] 依赖于 dp[i + 1][j - 1]，max(dp[i + 1][j], dp[i][j - 1]);
  11.         // 所以遍历顺序要 从下到上，从左到右遍历
  12.         for(int i = s.size() - 1; i >= 0; i--){
  13.             for(int j = i + 1; j < s.size(); j++){
  14.                 if(s[i] == s[j]){
  15.                     dp[i][j] = dp[i + 1][j - 1] + 2;
  16.                 }
  17.                 else{
  18.                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  19.                 }
  20.             }
  21.         }
  22.         // 注意，返回的dp需要根据动规五部曲来
  23.         return dp[0][s.size() - 1];
  24.     }
  25. };

55、动态规划总结篇

代码随想录 - 动态规划 - 54、动态规划总结篇