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

动态规划特点

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

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

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

1、动态规划基础题

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

爬楼梯（两道）：

2. dp[i] = dp[i - 1] + dp[i - 2]
   145、【动态规划】leetcode ——70. 爬楼梯：暴力法+动态规划（C++版本）：爬到第i阶楼梯可以依托于爬第i - 1阶楼梯的方式，或依托于爬到第i - 2阶楼梯的方式。

3. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i -2])
   146、【动态规划】leetcode ——746. 使用最小花费爬楼梯：递归法+迭代法（C++版本）：注意分清到第i层并不花费第i层的费用，只有跳到第i + 1层或第i + 2层才花费。找到跳到该层之前的最小费用方案。

机器人运动路径（两道）：

4. dp[i][j] = d[i - 1][j] + dp[i][j - 1]
   147、【动态规划】leetcode ——62. 不同路径：递归法+迭代法（C++版本）：到达i,j可以从i-1,j或i,j-1两个位置到达，依托于这两个位置上的可到达路径，再加上这条路径到达i,j。

5. dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
   148、【动态规划】leetcode ——63. 不同路径 II：递归法+迭代法（C++版本）：与上面的相比，多一个条件判定，只统计没有障碍物的位置，对于到达有障碍物的位置，不统计。

拆分数字：

6. dp[i] = max(d[i], max(j * (i - j), j * dp[i - j]))
   149、【动态规划】leetcode ——343. 整数拆分（C++版本）：d[i[表示数字i，拆分后可得到的乘积最大值，找到分成两个j * (i - j)和分成三个及以上j * dp[i - j]中的最大值，再和之前已得到的dp[i]相比，求出当前乘积最大值。

7. 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、打家劫舍问题

1. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
   163、【动态规划】leetcode ——198. 打家劫舍（C++版本）：不选当前而选择前一个i-1物品，选择当前物品i之间找最大值。

2. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])+分别对两个范围的数组进行dp更新求最大值
   163、【动态规划】leetcode ——213. 打家劫舍 II：环形列表线性化（C++版本）：将环形列表线性化，分成两种情况，求二者中的最大值。

3. 树形dp，max(偷当前结点， 不偷当前结点)
   165、【动态规划】leetcode ——337. 打家劫舍 III：记忆化递归+动态规划（C++版本）：树形dp需采用后序遍历，每次返回值为一个二维数组（0：不偷，1：偷），分别遍历左和右子树，然后将偷当前结点的结果与不偷当前结点的结果对比，取二者中的最大值。

4、股票问题

（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];}
};

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++版本）：仅允许进行一次买卖

2. 持有：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++版本）：可以进行多次买卖

3. 持有：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] = 0for(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];}
};

1. 第一次持有：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++版本）：可以进行两次买卖

2. 第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）含有冷冻期，可以进行有限次的买卖股票

1. 持有股票：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++版本）

5、子序列问题

（1）递增子序列问题

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

2. dp[i] = dp[i -1] + 1
   174、【动态规划/贪心算法】leetcode ——674. 最长连续递增序列 （C++版本）：每遇到一个连续递增子序列，就在前一个的基础上加一。

（2）编辑距离

1. dp[i][j] = dp[i - 1][j - 1] + 1
   175、【动态规划】leetcode ——718. 最长重复子数组 （C++版本）：比较到nums1[i -1]与nums2[j - 1]相等时，在前一个的基础上加一。

2. 当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 ——1143. 最长公共子序列（C++版本）：注意问题转化。

3. dp[i] = max(dp[i] + nums[i], nums[i])
   129、【动态规划/贪心算法】leetcode ——53. 最大子数组和（C++版本）：当前的加上之前的和从当前情况重新开始，二者之间取最大值。

4. 当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）的区别在于遇到不等时，固定子串，整体串前移一个

5. 当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缩一个的情况。

6. 思路一：当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++版本）

7. 相等：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）回文串

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++版本）：每次判定两段，然后基于长度情况和上一次结果的进行判定。

2. 当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++版本）