动态规划总结

参考来源：代码随想录

文章目录

• • 基础概念
  • 具体应用的问题
  • • 基础问题
    • 背包问题
    • 打家劫舍问题
    • 股票买卖问题
    • 子序列问题

基础概念

状态推导：动态规划中每一个状态一定是由上一个状态推导出来的。

动规五部曲：

1. 确定dp[i]或者dp[i][j]的含义。
2. 递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
3. 初始化dp数组：dp数组的第一个元素初始化，dp行列的初始化和其他位置初始化。
4. 确定遍历顺序：从前到后 或者 从后到前。
5. 打印：根据打印结果对比自己的预期判断是否解题正确。

debug：

1. 打印dp日志和自己想的一样（思路出错）：更换递推公式、修改初始化、遍历顺序和题目要求不符。
2. 打印dp日志和自己想的不一样（细节执行出错）：检查递推公式书写、初始化、打印顺序和预期的是不是一致。

具体应用的问题

基础问题

从状态的传递分析递推公式。当前点的值是根据之前的值推导而来。
求方法：dp[i] = dp[i-1] + dp[i-2];
求不同路径：dp[i][j] = dp[i-1][j] +dp[i][j-1]; dp[i][j]表示从(0, 0)到(i, j)的路径方法。
求整数拆分：dp[i] = max({ dp[i], (i-j) * j, dp[i-j] * j});
求二叉搜索树的个数：dp[i] = dp[j-1] * dp[i-j];

背包问题

0-1背包

每个物品的数量只有一个
二维数组：背包，物品遍历顺序任意
滚动数组：必须先物品再背包，背包的遍历顺序为倒序。

dp[j]含义：容量为j的背包所背的物品价值的最大值。
dp[j] = max(dp[i], dp[i-weight[i]] + value[i]);

应用：

1. 背包装物品的最大价值数：dp[j] = max(dp[j], dp[j-weight[j]]+vaule[i]);
2. 装满背包方法数：dp[j] += dp[j-nums[i]];
3. 能否装满背包：dp[j] = max(dp[j], dp[j-nums[j]]+vaule[i]); return dp[last] == target;
4. 装满背包的最小物品数：dp[j] = min(dp[j], dp[j-nums[i]]+1);

完全背包

每个物品的数量有无数个
滚动数组的背包和物品的遍历顺序任意，内层循环体必须从小到大，有累加效果。

应用：

1. 排列数：先背包再物品，给出一个集合和目标值。
2. 组合数：先物品再背包，给出一个集合和目标值。
3. 求满足的最小方法数
4. 单词拆分：截取字串与字符数组匹配再结合截取位置的dp值判断当前位置的dp值。

相关题目：

打家劫舍问题

1. dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2. 递推公式：dp[i]是由偷还是不偷第i房间决定的。
   如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，相邻的房间不偷，偷i-2个房间，获得金额是i-2房间最多偷窃的金额 加上 当前房间的金额。
   如果不偷第i房间，那么dp[i] = dp[i - 1]，即可以考虑前一个，第i-1房间。
   然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。

打家劫舍Ⅰ：房间是一列，不能偷相邻的房间 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。
打家劫舍Ⅱ：房间组成一个环，不能偷相邻的房间 i的范围就要考虑 从 [0, n-1] 和 从 [1, n]，即考虑第一个房间不考虑最后一间房，考虑最后一间房不考虑第一间房。
打家劫舍Ⅲ：房间组成一棵树。考虑左孩子和右孩子。树的递归三部曲和动规五部曲的结合。

股票买卖问题

1. dp[i][j]：dp[i][0] 表示第i天持有股票手里最多的钱，dp[i][1] 表示第i天不持有股票手里最多的钱。持有的状态 不等于 买入的状态，持有可能是今天买入，也可能是之前买入。
2. 递推公式：如何确定dp[i][0] 和 dp[i][1] 的值？
   dp[i][0]：第i天持有股票手里最多的钱，有两种情况。第一种，第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i][0] = dp[i - 1][0]。第二种，第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]。故dp[i][0] = max(dp[i - 1][0], -prices[i])。
   dp[i][1]：第i天不持有股票手里最多的钱。有两种情况，第一种，i-1天已经不持有，保持现状，即dp[i][1] = dp[i-1][1]。第二种，第i-1天持有，第i天卖出去，手里的钱是第i-1天手里持有的钱加上第i天卖出的钱，即dp[i][1] = dp[i-1][0] + prices[i]。故dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])。

买卖股票的最佳时机：只能买卖一次，dp[i][0] = max(dp[i-1][0], -prices[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]); dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
买卖股票的最佳时机Ⅲ：最多可以完成两笔交易，每个节点有五个状态。分别是状态不变、第一次持有、第一次不持有、第二次持有和第二次不持有。dp[i][0] = dp[i-1][0]; 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][i-1][2] - prices[i]); dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]);
买卖股票的最佳时机Ⅳ：最多可以完成k笔交易，为什么上一题最多完成两笔交易是五个状态，所以最多k笔交易是2*k + 1个状态，同Ⅲ的赋值。
买卖股票的最佳时机（含冷冻期）：卖出股票后，无法在第二天买入。有四个状态，买入股票、卖出股票、经历冷冻期、可以再次买入股票。dp[i][0] = max(dp[i-1][0], max(dp[i-1][2] - prices[i], dp[i-1][3] - prices[i])); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = dp[i-1][1]; dp[i][3] = max(dp[i-1[p2[, dp[i-1][3]);
卖出股票的时机（含手续费）：卖出时候需要添加手续费。保持的状态dp[i][0]和卖出时机Ⅱ一致，不保持状态需要加入手续费dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);

子序列问题

子序列（不连续）：if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
子序列（连续）：if(nums[i + 1] > nums[i]) dp[i+1] = dp[i] + 1;
编辑距离：

• 最长重复子数组：子数组是连续的。dp[i][j]：以i-1结尾的text1和以j-1结尾的text2的最长重复子数组。if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] =0;
• 最长公共子序列：不要求连续。if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

回文：dp[i][j]表示字符串[i, j]内回文串的个数或者最长回文串的长度。如，求字符串s中的最长回文子序列。