【算法刷题】动态规划算法题型及方法归纳

动态规划中每一个状态一定是由上一个出来，根据这个特点，可以在过程中，存储某一条件下的数据，当再次遍历该条件时，直接取该条件对应的数据即可，可以避免重复计算，减少时间。

辰阳星宇

2325人浏览 · 2023-02-25 22:01:30

辰阳星宇 · 2023-02-25 22:01:30 发布

动态规划特点

动态规划中每一个状态一定是由上一个状态推导出来，根据这个特点，可以在状态计算过程中，存储某一条件下的数据，当再次遍历该条件时，直接取该条件对应的数据即可，可以避免重复计算，减少时间。

核心思路： 学会倒着推理，从当前情况反推，会在上一步会由哪些情况到达这一步，从而分析出状态转移过程和递推公式。另一个就是在进行DFS遍历的时候，作为记录表，进行记忆化搜索。

解题步骤：动态规划五步曲

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

参考文章：动态规划最强总结篇！

1、动态规划基础题

斐波那契数列：

dp[i] = dp[i - 1] + dp[i - 2]
144、【动态规划】leetcode ——509. 斐波那契数：递归法+迭代法（C++/Python版本）：优化方法是让dp[1]始终指向最后，dp[0]指向前一位，用sum作为中间临时变量

爬楼梯：

dp[i] = dp[i - 1] + dp[i - 2]
145、【动态规划】leetcode ——70. 爬楼梯：暴力法+动态规划（C++/Python版本）：爬到第i阶楼梯可以依托于爬第i - 1阶楼梯的方式，或依托于爬到第i - 2阶楼梯的方式。
dp[i] = sum(dp[0], dp[1], … , dp[i-1])
204、【动态规划】牛客网 ——DP3 跳台阶扩展问题（Python版本）
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2])
146、【动态规划】leetcode ——746. 使用最小花费爬楼梯：递归法+迭代法（C++/Python版本）：注意分清到第i层并不花费第i层的费用，只有跳到第i + 1层或第i + 2层才花费。找到跳到该层之前的最小费用方案。

运动路径问题：

dp[i][j] = d[i - 1][j] + dp[i][j - 1]
147、【动态规划】leetcode ——62. 不同路径：递归法+迭代法（C++/Python版本）：到达i,j可以从i-1,j或i,j-1两个位置到达，依托于这两个位置上的可到达路径，再加上这条路径到达i,j。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
148、【动态规划】leetcode ——63. 不同路径 II：递归法+迭代法（C++/Python版本）：与上面的相比，多一个条件判定，只统计没有障碍物的位置，对于到达有障碍物的位置，不统计。
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
192、【动态规划】leetcode ——64. 最小路径和：回溯法+动态规划（C++/Python版本）：到达(i, j)尽可能由两种情况组成，初始化时边界上的顺路只会有一种情况。

拆分数字：

dp[i] = max(d[i], max(j * (i - j), j * dp[i - j]))
149、【动态规划】leetcode ——343. 整数拆分（C++/Python版本）：d[i[表示数字i，拆分后可得到的乘积最大值，找到分成两个j * (i - j)和分成三个及以上j * dp[i - j]中的最大值，再和之前已得到的dp[i]相比，求出当前乘积最大值。
dp[i] += dp[j - 1] * dp[i - j]
150、【动态规划】leetcode ——96. 不同的二叉搜索树（C++版本）：以i为根节点，构造的BST个数 = 以j - 1为根节点的个数 * 以i - j为根节点的个数，再让j从0到i的各种情况求和。

2、背包问题

背包问题是在规定背包容量为j的前提下，每个物品对应的体积为v[i]，价值为w[i]，从物品0到物品i中选择物品放入背包中，找出符合某种要求的价值。

（1）背包问题种类

01背包：每种物品只能选择1个。
完全背包：每种物品可以选择无限个。
多重背包：每种物品最多可选s[i]个。

（2）递推公式

01背包：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
完全背包：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
多重背包：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i], dp[i - 1][j - 2*v[i]] + w[i] + ... + dp[i - 1][j - s[i]*v[i]] + s[i]*w[i])

（3）滚动数组遍历顺序：

01背包：从大到小
完全背包：从小到大
多重背包：在01背包的基础上，从大到小，多一层for循环选物品个数

详细内容：【动态规划】背包问题题型及方法归纳

3、线性dp

（1）打家劫舍问题

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
163、【动态规划】leetcode ——198. 打家劫舍（C++版本）：不选当前而选择前一个i-1物品，选择当前物品i之间找最大值。
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])+分别对两个范围的数组进行dp更新求最大值
163、【动态规划】leetcode ——213. 打家劫舍 II：环形列表线性化（C++版本）：将环形列表线性化，分成两种情况，求二者中的最大值。
树形dp，max(偷当前结点，不偷当前结点)
165、【动态规划】leetcode ——337. 打家劫舍 III：记忆化递归+动态规划（C++版本）：树形dp需采用后序遍历，每次返回值为一个二维数组（0：不偷，1：偷），分别遍历左和右子树，然后将偷当前结点的结果与不偷当前结点的结果对比，取二者中的最大值。

（2）股票问题

1）仅能进行一次和无限次的买卖股票

设置两个dp，dp[i][0]表示持有股票时，具有的最大收益；dp[i][1]表示不持有股票时，具有的最大收益。

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n + 1, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        
        for(int i = 1; i < n; i++) {
        	// 仅能进行一次买卖操作：
			// dp[i][0] = max(dp[i - 1][0], - prices[i]);
        	// 可以进行多次买卖操作：
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        return dp[n - 1][1];
    }
};

持有：dp[i][0] = max(dp[i-1][0], -prices[i])、不持有：dp[i][1] = max(dp[i-1], dp[i][0] + prices[i])
168、【贪心算法】leetcode ——121. 买卖股票的最佳时机：dp数组+变量优化（C++版本）：仅允许进行一次买卖
持有：dp[i][0] = max(dp[i-1][0], dp[i][1] - prices[i])、不持有：dp[i][1] = max(dp[i-1], dp[i][0] + prices[i])
130、【贪心算法/动态规划】leetcode ——122. 买卖股票的最佳时机 II（贪心算法）（C++版本）：可以进行多次买卖
持有：dp[i][0] = max(dp[i-1][0], dp[i][1] - prices[i])、不持有：dp[i][1] = max(dp[i-1], dp[i][0] + prices[i] - fee)
172、【动态规划】leetcode ——714. 买卖股票的最佳时机含手续费（C++版本）：相比于2多了一个扣除手续费。

2）可以进行有限次的买卖股票

模板：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty() || prices.size() == 1)                  return 0;
        int n = prices.size();
        vector<vector<int>> dp(n + 1, vector<int>(2 * k + 1));
        // dp[0][0] = 0
        for(int i = 1; i < 2 * k + 1; i += 2) {
            dp[0][i] = -prices[0];            // 2*k-1为持有为-prices[0]，2*k为不持有为0。
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < 2 * k + 1; j += 2) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }

        return dp[n - 1][2 * k];
    }
};

第一次持有：dp[i][1] = max(dp[i - 1][1], -prices[i])，第一次不持有：dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])，第二次持有：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])
169、【贪心算法】leetcode ——123. 买卖股票的最佳时机 III：二维数组+一维数组（C++版本）：可以进行两次买卖
第k次持有：dp[i][2 * k - 1] = max(dp[i - 1][2 * k - 1], dp[i - 1][2 * k - 2] - prices[i])，第k次不持有：dp[i][2 * k] = max(dp[i - 1][2 * k], dp[i - 1][2 * k - 1] + prices[i])
170、【贪心算法】leetcode ——188. 买卖股票的最佳时机 IV：二维数组+一维数组（C++版本）：可以进行k次买卖

3）含有冷冻期，可以进行有限次的买卖股票

持有股票：dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i])、不持有股票且明天将为冷冻期：dp[i][1] = dp[i][0] + prices[i]、不持有股票且明天不为冷冻期：dp[i][2] = max(dp[i - 1][2], dp[i - 1][1])
171、【动态规划】leetcode ——309. 最佳买卖股票时机含冷冻期（C++版本）

（3）子序列问题

1）递增子序列问题

dp[i] = max(dp[i], dp[j]+1)
173、【动态规划】leetcode ——300. 最长递增子序列（C++版本）：按顺序遍历，当对比发现当前元素大于前方某一位置元素时，就在该位置元素已有的最长递增子序列长度上加一和当前元素已记录的最长递增子序列长度对比，最大值。
dp[i] = dp[i -1] + 1
174、【动态规划/贪心算法】leetcode ——674. 最长连续递增序列（C++版本）：每遇到一个连续递增子序列，就在前一个的基础上加一。

2）编辑距离

dp[i][j]表示含义：以word1[i - 1][j - 1]为结尾的xxxxx。

dp[i][j] = dp[i - 1][j - 1] + 1
175、【动态规划】leetcode ——718. 最长重复子数组（C++版本）：比较到nums1[i -1]与nums2[j - 1]相等时，在前一个的基础上加一。
当text1[i - 1] == text2[j - 1]时，令dp[i][j] == dp[i - 1][j - 1] + 1；当不等于时，dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
176、【动态规划】leetcode ——1143. 最长公共子序列（C++版本）：与1的区别在于，2中不要求子序列连续。
拓展题： 177、【动态规划】leetcode ——11035. 不相交的线（C++版本）：注意问题转化。
dp[i] = max(dp[i] + nums[i], nums[i])
129、【动态规划/贪心算法】leetcode ——53. 最大子数组和（C++版本）：当前的加上之前的和从当前情况重新开始，二者之间取最大值。
当text1[i - 1] == text2[j - 1]时，令dp[i][j] == dp[i - 1][j - 1] + 1；当不等于时，dp[i][j] = dp[i][j - 1]
178、【数组/动态规划】leetcode ——392. 判断子序列：双指针+动态规划（C++版本）：思路与（2）的区别在于遇到不等时，固定子串，整体串前移一个
当s[i - 1] == t[j - 1]时，令dp[i][j] == dp[i - 1][j - 1] + dp[i-1]dp[j]；当不等于时，dp[i][j] = dp[i][j - 1]
178、【动态规划】leetcode ——115. 不同的子序列（C++版本）：与（5）中不同的在于此时要进行累计，因此需要再加上t维持不动s缩一个的情况。
思路一：当word1[i - 1] == word2[j - 1]时，令dp[i][j] == dp[i - 1][j - 1]；当不等于时，dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)
思路二：在求最长公共子序列的基础上，得到长度，也能搞两个序列总长度减去二倍的最长公共子序列长度。
180、【动态规划】leetcode ——583. 两个字符串的删除操作：两种动态规划思路（C++版本）
相等：dp[i][j] = dp[i - 1][j - 1]，不相等：1）增：dp[i][j - 1] + 1；2）删：dp[i - 1][j] + 1；3）改：dp[i - 1][j - 1] + 1
181、【动态规划】leetcode ——72. 编辑距离（C++版本）：主要是两个状态四个操作，相等时对应状态一种操作，不相等时对应状态三种操作。

3）回文串

dp[i][j]含义：以下标i-j之间的回文串情况，状态操作是i + 1和·就j- 1。

当s[i]==s[j]时，若j - i <= 1，则dp[i][j]=true；若j - i > 1且dp[i-1][j+1]==true，则dp[i][j]=true，否则为false。当s[i]!=s[j]时，则dp[i][j]=false
182、【动态规划/数组】leetcode ——647. 回文子串：动态规划+双指针（C++版本）：每次判定两段，然后基于长度情况和上一次结果的进行判定。
当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2；当s[i]!=s[j]时，dp[i][j]=max(dp[i][j-1],dp[i+1][j])。
182、【动态规划】leetcode ——516. 最长回文子序列（C++版本）

4、区间dp

区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。

区间dp模板

for(int i = 1; i <= n; i++) {                 // 枚举区间长度
    for(int j = 1; j <= n - i + 1; j++) {     // 枚举起始点
        int l = i, r = j + i - 1;             // 设置左端点和右端点
        for(int k = l; k <= r; k++) {         // 枚举分割点，找到最优分割情况
            dp[l][r] = operate(dp[l][r], dp[l][k] + dp[k + 1][r] + x);  // 分区间进行某种消除操作后与已有情况对比，找到最优解
        }
    }
}

dp[i][j]=min(dp[i][j], dp[i][k] + dp[k + 1][j] + 区间和)
190、【动态规划】AcWing ——282. 石子合并（C++版本）：区间长度由小到大枚举，每次遍历分割点，加上区间和找到最小代价之和。
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
189、【动态规划】leetcode ——312. 戳气球（C++版本）：首尾添加元素，逆向思考从最后一个戳破时，得到的最大硬币数量。自下而上，从左到右遍历。

4、计数类dp

dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]
191、【动态规划】AcWing ——AcWing 900. 整数划分：完全背包解法+加减1解法（C++版本）：集合划分成两部分，一部分是j中的数最小值为1，另一部分时j中的数最小值大于1。从最小值为1的数转化来的方案数不变，从最小值大于1的数转化来的，按照j个数各减去1之后的方案数转化而来。

5、状态压缩dp

在这里插入图片描述
状态压缩会用二进制位来存储状态信息，在状态计算时，将整数转化为二进制形式进行计算。

可表示的状态就是 $2^n$ 个。

状态压缩常用的几种操作
在这里插入图片描述

dp[i][j] += dp[i -1][k]
193、【动态规划】AcWing —— 291. 蒙德里安的梦想：状压dp详细解析（C++版本）：将问题转化为找到合法的横着放的长方体摆放情况，先根据方框的构架预处理各个合法情况，然后再用dp进行合法判定转移计算。
dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]))
195、【动态规划】AcWing —— 91. 最短Hamilton路径（C++版本）：先遍历状态，再遍历点，每次找到是从k到j，让原点到j的距离最短还是从到原先j的距离最短。

6、树形dp

树形dp就是构建要在一颗树的结构上构建dp进行记录，常用的操作是选择当前叶子或者不选择当前当前叶子两种操作。常去结合回溯遍历、后序遍历等进行实现。

模板

// 不选当前叶子的操作
dp[i][0] = operation0(dp[i][0], dp[j][0], dp[j][1], weight[i], weight[j])		
// 选当前叶子的操作
dp[i][1] = operation1(dp[i][0], dp[j][0], dp[j][1], weight[i], weight[j])

max(偷当前结点，不偷当前结点)
165、【动态规划】leetcode ——337. 打家劫舍 III：记忆化递归+动态规划（C++版本）：树形dp需采用后序遍历，每次返回值为一个二维数组（0：不偷，1：偷），分别遍历左和右子树，然后将偷当前结点的结果与不偷当前结点的结果对比，取二者中的最大值。
dp[u][1] += dp[j][0]、dp[u][0] += max(dp[j][1], dp[j][0])
196、【动态规划】AcWing —— 285. 没有上司的舞会（C++版本）：从根节点向下遍历，为1时代表选取当前节点，则孩子节点不能选；为0时代表不选当前节点，则从选和不选孩子节点之间选择一个。

7、记忆化搜索

记忆化搜索就是在DFS深度优先遍历的基础上，加上了一个记录表，可以让在遍历的时候不用再重复遍历已经遍历过的位置。
在这里插入图片描述

dp[i] = dp[i - 1] + dp[i - 2]
144、【动态规划】leetcode ——509. 斐波那契数：递归法+迭代法（C++版本）：使用记忆化搜索，对于探寻过的地方直接剪枝。
dp[x][y] = max(dp[x][y], dfs(a, b) + 1)
197、【动态规划】AcWing —— 901. 滑雪（C++版本）：枚举所有起始点，探寻上下左右四个方向，使用dfs后序遍历找到所有可能结果，用dp记录探寻过程。
dp[i] = min(dp[i - 1] + cost[0], dp[i - 7] + cost[1], dp[i - 30] + cost[2])
198、【动态规划】leetcode ——983. 最低票价：记忆化搜索（C++版本）：记录已遍历过的天数中最低票价情况，使用一个布尔类型变量记录是否有某一天需要出行。