动态规划的套路: 从入门到精通到弃坑 #

本文是视频残酷刷题群算法小讲座：动态规划的套路的学习笔记.

动态规划的思考艺术 #

暴力枚举为什么不优秀? #

• 大量的重复计算
• 需要具体的路径

动态规划对比暴搜的优点? #

• 只关心状态, 也就是路径的数目
• 利用子问题向上求解
• 舍弃了冗余信息(路径的具体实现), 只关心状态的变化

动态规划适用的场景? #

能将问题拆分为子问题, 同时具有两大特点:

无后效性 #

• 一旦状态确定, 就不用关心"如何计算出状态";
• 想要确定一个状态, 只需要知道某些过去的状态; 至于过去的状态是怎么计算出的, 对问题没有任何影响.

最优子结构 #

• 定义状态时已经蕴含了"最优";
• 大问题的最优解可以由小问题的最优解推导出.

动态规划的常见套路 #

第Ⅰ类基本型 时间序列 #

特点 #

给出一个序列(数组/字符串), 其中每一个元素可以认为是"一天", 并且"今天"的状态只取决于"昨天"的状态.

解法 #

• 定义 $dp[i]$ , 表示第 $i$ 轮的状态;
• 设法将 $dp[i]$ 与 $dp[i - 1]$ 产生联系;
• 最终结果为 $dp[last][j]$ 中的某种最优值.

例题 #

LeetCode-198 打家劫舍 LeetCode-213 打家劫舍 II LeetCode-123 买卖股票的最佳时机 III LeetCode-309 最佳买卖股票时机含冷冻期 LeetCode-376 摆动序列 注: 不知道题目有没有修改过, 依据2022-05-06的题意, 视频中给出的状态转移方程的说明是错误的, 这道题严格来说不属于时间序列型这一分类, 我会专门用一篇文章分析这道真正的状态转移方程. LeetCode-276 栅栏涂色 注: 这道题是会员题, 与 LeetCode-1289类似. LeetCode-1289 下降路径最小和 II LeetCode-487 最大连续1的个数 II 注: 这道题是会员题. LeetCode-1186 删除一次得到子数组最大和

思考题 #

给 $N$ 个房子, 涂白色和涂黑色的花费分别是 $a$ 和 $b$ , 要求不能有连续三间房子涂同一种颜色, 求喷涂所有房子的最小价格.

第一眼看上去不是前面同类型的时间序列型问题(涉及前两个时间点的状态), 但是我们可以这样设定状态: 结尾有连续 $1$ 间为黑色, 结尾有连续 $2$ 间为黑色, 结尾有连续 $1$ 间为白色, 结尾有连续 $2$ 间为白色. 这样就可以像之前那样推导了. (注意状态必须是互斥且包含所有情况的.) 状态转移方程如下:

dp[i][0] = min(dp[i - 1][2], dp[i - 1][3]) + blackCost;
dp[i][1] = dp[i - 1][1] + blackCost;
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + whiteCost;
dp[i][3] = dp[i - 1][2] + whiteCost;

第Ⅱ类基本型 时间序列加强版 #

特点 #

给出一个序列(数组/字符串), 其中每一个元素可以认为是"一天", 但"今天"的状态和之前"某一天"有关, 需要挑选.

解法 #

• 定义 $dp[i]$ , 表示第 $i$ 轮的状态; 一般这个状态要求与元素 $i$ 直接有关.
• 设法将 $dp[i]$ 与 $dp[i’]$ 产生联系; $i’$ 要求小于 $i$ (否则违反了无后效性).
• 最终结果为 $dp[i]$ 中的某一个.

例题 #

LeetCode-300 最长递增子序列 LeetCode-673 最长递增子序列的个数 LeetCode-368 最大整除子集 LeetCode-1105 填充书架