动态规划

1 解题步骤

Dynamic Programming 动态规划

真正理解 DP 应该注意一下几点：

1. DP 数组中每一个值，或者索引的意义
2. 递推公式
3. DP 数组的如何初始化
4. 遍历顺序
5. 打印 DP 数组（主要用于分析错误）

1.1 什么时候用

1. 判断所有可能的状态中（图）是不是有环，有环一定不是 DP
2. 数据量极大的情况下不太能用 DP

DP 的核心是，递推关系要固定不变，能找到让关系保持不变的 dp 数组定义，这点也是最难的

2 背包问题

2.1 零一背包 （二维数组）

给定 n 件物品，每件物品有价值 value[i] 和重量 weight[i]
在容量为 W 的背包中选择若干件物品，使得总价值最大，每件物品最多选一次。

先用没有空间简化的方式进行分析（二维 dp）

1. 数组的定义：[0, i] 个物品，任选放入容量为 j 背包中的最大价值为 dp[i][j]

2. 递推公式：

   • 不放物品 i 则和 i - 1 一致
   • 如果放入 dp[i - 1][j - weight[i]] + value[i]，也就是不放入之前的最大价值（注意要改重量）+ 放入后的最大价值
   • 取上述两种情况的最大值，就是递推公式
   • 记得需要检查 j - weight[i]] + value[i]是否成立，也就是当前容量是否能够放入这个物品

3. 初始化需要先分析递推公式需要的前置条件

   • 需要的是 [i - 1][j] 或者 [i - 1][j - n] 的数据，因此初始化横纵坐标即可
   • 其他位置初始化，实际上这个值和后面的求值没有关系，初始化为任何值都可以
   • 其实初始化还可以横纵坐标都用 0 作为边界条件，不过代码随想录里并没有这么做
4. 遍历顺序，根据递推公式前置条件可以得到，实际上二维 dp 是没有顺序要求的，正序倒序以及背包物品顺序都可以颠倒

// 假设：dp 的维度是 dp[N][C+1]，并且已初始化为 0
// dp[i][j]：用前 i 个物品（下标 0..i），在容量 j 下的最大价值

for (int j = 0; j <= C; j++) {
    if (j >= w[0]) dp[0][j] = v[0];
    // else dp[0][j] = 0;  // 已初始化可省略
}

for (int i = 1; i < N; i++) {
    for (int j = 0; j <= C; j++) {
        dp[i][j] = dp[i-1][j];  // 不选第 i 个，先继承
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);  // 选第 i 个
        }
    }
}

2.2 零一背包（滚动数组）

可以发现一个问题，就是 dp[i] 一直使用的是 dp[i - 1] 相关的数据进行计算的

但是要注意遍历的顺序，检查递推公式：dp[i - 1][j - weight[i]] + value[i] 和 dp[i - 1][j] 其中之一，可以发现j 依赖于 上一轮次的 j 或者 j - weight[i]，这两个都是小于等于 j 的，因此 dp[j] 的遍历要用到上一轮的更小值，应该是从大到小遍历才可以！

1. 数组定义：在第 i 次循环中dp[j] 容量为 j 的背包的最大价值
2. 递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) （注意其实 i 这个索引还是存在的，只是把 p 数组压缩一个维度）
3. 初始化：dp[0]肯定是 0，其他数值初始化为可能的数值中的最小值（为了防止覆盖其他值），看题目，一般也是 0
4. 遍历顺序：先遍历物品数量，再遍历背包容量，第二层循环需要倒序（因为不可以对依赖项进行覆写）

代码部分可以参考本文中 分割等和子集 题目

// w 和 v 下标从 0 开始
for (int i = 0; i < N; i++) {
    for (int j = C; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

2.3 完全背包

每一个物品可以使用无数次的背包

对于二维的情况下，直接改成就是完全背包，表示允许重复选取某一个数

dp[i][j] = max(
    dp[i-1][j],                 // 不选第 i 个物品
    dp[i][j - w[i]] + v[i]      // 选第 i 个物品（可重复）
)

把内层 for 循环改成正序遍历就可以让物品使用无限次

for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= C; ++j) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

这里要明确清楚为什么，因为在正序遍历的时候 dp[j - w[i]] + v[i]这个数值中的 dp[j - w[i]] 是在本轮（外层 i 循环）之前遍历的，有可能是已经添加过物品 i 的一个状态。这时候的递推是基于本轮的状态实现的，可以在此基础上再添加一个物品 i，因此就构成了每个物品可以无限取用的情况，也就是完全背包

另外要注意一点：纯完全背包的遍历顺序（物品和背包）是可以颠倒的！

原因就是一个：递推公式中可以由前面的数值推出当前的数值，我的建议是如果理解的话还是需要手动模拟一下横纵的顺序，就可以发现颠倒顺序后仍然可以用前面的状态推出当前的状态

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

2.4 完全背包的排列组合

但是如果涉及到了排列组合问题，就会导致遍历顺序需要注意

假设我们的物品重量为 w[] = [1, 2, 3];，对于取物品恰好满足和为 target 的题目，递推公式为dp[j] += dp[j - w[i]];

这个递推公式是通用的，关键在于 dp[j - w[i]]代表的数值是什么

对于 先遍历物品后遍历背包的场景（01 背包通用方式）：

1. 在 1 物品选择依次放满所有的背包
2. 在 12 物品中选择依次放满，这个情况下只会有先 1 后 2的放入情况

意思是放入 2 以后，必定只会放入 >= 2 的物品，不会再回去放入 1，这种情况是组合

对于 先遍历背包后遍历物品的场景：

我认为这个有点抽象，所以这里用了手写的方式来解释

这里 dp 数组中是一个个确认过去的，内层循环中会反复对同一个 dp[j] 进行状态的累加，因此参考下图可以发现重叠的问题

就是因为取物品的顺序不是固定的，i 的循环表示最后补上这个物品（没有圈的数值），但这就会导致每个物品都有可能为那个“补充值”，但是补充值本身会在 0 + j的情况下被计算一次：

举例来说：3 = 1 + 2， 这里的 2 当做“补充值”，表示在所有和为 1 的情况上末尾补充一个 2 可以达成和为 3，但是当我们求补充值为 1 的时候，计算所有和为 2 的情况个数的时候，会和补充值为 2 的情况重复

3 股票问题

股票问题的关键仍然在于 dp 数组的定义

定义 dp[i][0] 和 dp[i][1] 分别表示股票的持有和未持有，而不是统计买入与卖出，这是唯一的关键

4 子序列问题

如果是连续子序列问题，可以查看 KMP 算法

如果是两个字符串相关的比较，将连个字符串构成一个 二维的数组可罗列所有的状态

一般来说永远推荐把 dp[j]定义为 nums[j - 1]为结尾的 xxx 状态，这样可以省去一个初始化特判的过程

之后的 for 循环只需要从 1 遍历到 nums.size() + 1即可

4.1 LCS 最长子序列

最长子序列问题：考虑删除这唯一一个操作

删除表示不在某一个字符串中考虑这个字符，也就是在对应的 dp 数组中向上回退一个数字

不同的题目需要注意删除这个操作对 dp 数组内容的影响

4.2 编辑距离

编辑距离就是 删除操作会导致一个操作数 + 1

编辑距离的另一个主要特点就是： 操作是相互的，也就是删除 a 的一个元素，等价于给 b 增加一个元素

另外，如果替换一个字符，等于消耗一个操作，将两个字符变成相等

因此总结来看，终究还是删除和相等两种操作，关键在于需要学会定义 dp 数组为 nums[i - 1] 对应的 xxx

4.3 回文串

回文串的特点是他的状态转移不是取决于某一个值的加入，而是第一个值和最后一个值的加入

意思是状态转移时设定 dp[i][j] 代表 [i, j) 的字符串是不是回文串的时候，其依赖的状态是 dp[i + 1][j - 1]

5 经典题目

之前从来没有接触过动态规划，所以可能选择的题目相对多一些

5.1 爬楼梯

LeetCode 70

统计爬楼梯次数，例如 第 3 层只能由第 2 层或者第 1 层爬上来，这就构成了递推关系

1. dp 数组：索引代表第几个台阶，数值代表需要的步数
2. 递推公式： 上两个台阶的次数求和
3. 数组初始化：dp[1] = 1, dp[2] = 2
4. 遍历顺序：顺序

如果使用循环变量的方式，实际使用方法是和斐波那契的反过来的（因为初始值不同了所有有影响）

其实 dp 的题目也不一定要优化，那样初始化逻辑会更加清晰明了

class Solution {
public:
    int climbStairs(int n) {
        // 同样使用两个内存就可以了
        vector<int> dp(2, 0);
        dp[0] = 1;
        dp[1] = 2;

        int ret = 0;
        if (n < 3) return n;
        for (int i = 2; i < n; i++) {
            // 注意这里的滚动
            ret = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = ret;
        }
        return ret;
    }
};

5.2 不同的二叉搜索树

LeetCode 96

可能从这里开始递归关系相对开始复杂了

遍历所有数值作为根节点，然后左右子树的 dp 数量相乘

这里似乎能够看出来，dp 的本质是用过去的状态推导现在的状态（有点像递归经典汉诺塔？）

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1 , 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j <= i; j++) {
                // 左右子树分别数量相乘
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

5.3 分割等和子集

LeetCode 416

这是一个 01 背包问题，将数值同时视作价值和重量，在理解这个的问题上花了很多时间，实际上是在给定的上限中尽可能的取到最靠近上限的指标，只不过上限和指标都是同一个数值组成的

如果把 容量和价值都设置为数值，那么就指的是在给定的上限下，取到最靠近上限的一个值

dp 数组的含义是背包容量为 j 能够装下物品的最大价值，

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 01 背包，容量和价值相等，滚动数组方式
        int sum = 0;
        for (int& a : nums) sum += a;
        if (sum % 2) return false;
        // 容量下标直接代表容量，所以要 + 1
        int items = nums.size();
        int volume = sum / 2;
        vector<int> dp(volume + 1, 0);

        // 初始化应该全部是0，已经完成了
        for (int i = 0; i < items; i++) {
            for (int j = volume; j>= nums[i]; j--) {
                // 这里要保证当前物品放得进去，并把判断放进循环
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); // 这里第二个 num[i] 是价值
            }
        }
        return dp[volume] == volume;
    }
};

5.4 目标和

LeetCode 494

本题的关键点在于，所有的正数之和应该等于 (sum + target) / 2， 随后转化为 01 背包问题

指定 dp 数组的含义是 dp[i][j] 代表 选取前 i 个物品构成和为 j 的可能性计数

可以得到递推公式 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，分别表示是否加入当前数组

随后就可以简化为 一维数组

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int &a : nums) sum += a;
        // 如果 target 绝对值大于 sum，肯定无解
        if (abs(target) > sum) return 0;
        if ((sum + target) % 2 != 0) return 0;
        int pos = (sum + target) / 2;  // 所有被赋予正号的数之和
        
        vector<int> dp(pos + 1, 0);
        dp[0] = 1; // 装满容量为 0 的背包有 1 种方法：什么都不选

        for (int i = 0; i < (int)nums.size(); i++) {
            for (int j = pos; j >= nums[i]; j--) {
                // 当前位置 j 的方案数 += 选择当前物品后的方案数
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[pos];
    }
};

5.5 完全平方数

LeetCode 279

注意递推关系， + 1 并取最最小值

class Solution {
public:
    int numSquares(int n) {
        // 完全背包，最小值
        int max = sqrt(n) + 1;
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= max; i++) {
            int sq = i * i;
            for (int j = sq; j <= n; j++) {
                    dp[j] = min(dp[j], dp[j - sq] + 1); // 不要忘了这里 + 1
            }
        }
        return dp[n];
    }
};

5.6 单词拆分

本质还是把每一个小词当作一个物品，背包容量是整个字符串

这里可以记忆一下 string 的库函数比较

s.compare(pos, len, target) 表示 从字符串 s 的位置 pos 开始，取长度 len 的字串进行比较 target

注意这个返回值是 int 不是 bool ，在两者相等的时候返回 0

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int j = 1; j <= n; j++) {
            for (const auto& w : wordDict) {
                int len = w.size();
                if (j >= len && dp[j - len]) {
                    // s 的子串 [j-len, j) 是否等于 w
                    if (s.compare(j - len, len, w) == 0) {
                        dp[j] = true;
                        break;
                    }
                }
            }
        }
        return dp[n];
    }
};

5.7 打家劫舍 III

LeetCode 337

树形 dp 的基础题目，之前一直使用的是在一维数组中进行 dp 的规划，现在是树形中的

通过递归可以实现每个层单独一个 dp 数组，但是因为递归会自动保留参数，所以每层中间信息是共享的

dp[0] 是不偷， dp[1] 是偷的最大金钱

class Solution {
public:
    int rob(TreeNode* root) {
        // 左右的孩子节点，递归返回 dp 数组
       vector<int> ret = reverseTraversal(root);
       return max(ret[0], ret[1]);
    }

    vector<int> reverseTraversal(TreeNode* root) {
        // 0 代表没有偷， 1 代表偷了
        vector<int> dp(2, 0);
        if (root == nullptr) return dp;

        vector<int> left = reverseTraversal(root->left);
        vector<int> right = reverseTraversal(root->right);

        dp[1] = left[0] + right[0] + root->val;
        dp[0] = max(left[0], left[1]) + max(right[0], right[1]); // 这里要注意，取最大的，不一定要偷左右孩子
        return dp;
    }
};

5.8 买卖股票的最佳时机

LeetCode 121

这道题简单，但是我们抛砖引玉一下，用 dp 的方法来计算这一类的问题

这个 dp 数组的定义比较抽象，主要是为了能够包含所有的状态（例如定义第 i 天卖出的收益，那么什么都不做，怎么用第 i 天卖出这个定义表示呢？）

1. dp[i][0] 表示第 i 天不持有这个股票的最大现金，而 dp[i][1]表示持有下的最大现金，注意这里是持有，不一定是当天进行了买卖
2. 初始化：dp[0][0] = 0, dp[0][1] = - price[0]

3. 递推公式：

   • dp[i][0] = dp[i - 1][0] 表示今天不执行任何操作
   • dp[i][0] = dp[i - 1][1] + price[i] 表示把股票卖了
   • dp[i][1] = dp[i - 1][0]- price[i] 表示第 i 天买入了这个股票（本题只买卖一次，所以必须等于 - price[i]）
   • dp[i][1] = dp[i - 1][1] 不执行任何操作
   • 上述分别取最大值就是递推公式
4. 递归顺序：常规从前到后即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 
            dp[i][1] = max(dp[i - 1][1], - prices[i]); // 只允许买入一次
        }
        return dp[prices.size() - 1][0];
    }
};

5.9 最长递增子序列

LeetCode 300

这题目是很经典的 dp 题目，难点在怎么定义 dp 数组

很多题目都用 结尾 作为 dp 数组的定义，实际原因是，这类题型只有末尾才能够构成严格递推关系，因为很多时候长度不固定的，定义开头无法确定递推；但是由于前 n 个的最优解一定包含在前 n+1 当中

1. 定义：以 num[i] 结尾的最长子序列的长度，因为计算递增一定要有一个末尾固定才好算
2. 递推公式：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1; ，每一个都要把前面的数字的全部统计一次
3. 初始化：序列的长度肯定至少都是 1，剩下的取最大值就可以更新
4. 遍历顺序：根据公式肯定是从前向后

这是这道题的 dp 写法，复杂度 $O(n^2)$ 这道题实际上还有个二分优化的方法，不过日后再写吧

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp
        vector<int> dp(nums.size(), 1); // 全部初始化为1
        int ret = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) 
                    // 从前面取一个末尾小于本体，然后 + 1
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

5.10 最长重复子数组

LeetCode 718

这里能够总结出一个经验，就是把无效的状态全部都塞进 0 的位置，可以省去很多麻烦的初始化步骤

例如本题目把 dp[i][j] 定义为 下标 [i - 1] [j - 1] 的数组的最长重复子数组，可以省去初始化部分

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        // 初始化注意要 + 1
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        int ret = 0;
        // 从 1 开始，不用考虑边界，同时覆盖了所有可能的解
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
};

5.11 编辑距离

LeetCode 72

编辑距离，这是一维优化后的解法，详细可以参考开头的内容

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 编辑距离 一维优化
        // 尤其注意在横纵的初始值都不是 0 的时候，纵向初始值在 1 维 dp 每一轮都要修正
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);
        for (int j = 0; j <= n; j++) dp[j] = j;
        for (int i = 1; i <= m; i++) {
            int pre = dp[0]; // 对于本轮来说是 dp[1 - 1][j - 1];
            dp[0] = i;  // dp[0] 需要随着 i 轮次进行更新，为下一轮的 pre 准备
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j]; // 保存下一回的 dp[i - 1][j - 1];
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = pre; // 来自上一回的 dp[i - 1][j - 1]
                } else {
                    dp[j] = min({dp[j - 1], dp[j], pre}) + 1;
                }
                pre = tmp;
                // cout << dp[j] << ' ';
            }
            // cout << endl;
        }
        return dp[n];
    }
};

5.12 最长回文子序列

LeetCode 516

看到子序列基本上就是 dp 的解法了

具体的状态转移可以参见开头写的子序列问题，这是 LeetCode 的官方解法

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

6 总结

这类题目的难点在于是不是能够合理的猜想出一个可行的 dp 数组定义，这很依赖经验

另外，如果有了一个 dp 数组定义的想法了，我的建议是写一个 一般一点的例子 来列出整个 dp 数组

我的意思是，相比于对着逻辑进行直接推到状态转移的关系，有时候瞪眼法看看数组找规律也许很有效（也就是猜一个转移过程来证明一下，对于复杂一点的题目可能会好写一点）