动态规划与贪心

一句话：动态规划和贪心都是”不穷举所有解，靠某个性质剪掉大部分选择”，区别在于动态规划把每一步的所有候选都存下来供后面复用，贪心直接证明”每一步只保留一个候选就够了”。判断一道题该用哪个，比写出代码本身更考验功力，也是这一页真正的价值所在。

动态规划：重叠子问题 + 最优子结构

70-爬楼梯、198-打家劫舍、300-最长递增子序列、72-编辑距离 能用 DP 的前提是两条同时成立：子问题会被重复计算（不存下来就要反复重算，这是”重叠子问题”），且整体最优解可以由子问题的最优解直接推出（这是”最优子结构”）。

写 DP 的固定顺序：先想清楚 dp[i]（或dp[i][j]）代表什么，再推转移方程，最后确定边界——很多人反过来先写循环再拼凑转移方程，容易在状态定义模糊的情况下把自己绕晕。72-编辑距离 的 dp[i][j] 代表”s1 的前 i 个字符变成 s2 的前 j 个字符所需的最少操作数”，转移时枚举”增/删/改”三种操作对应的子问题，这个定义清楚了，转移方程几乎是抄状态定义抄出来的。

背包类是 DP 里最容易搞混维度的一类（322-零钱兑换、416-分割等和子集、139-单词拆分）：322 每种硬币可以用无限次（完全背包），416 每个数字只能用一次（0/1 背包），循环顺序（外层物品/内层容量 vs 外层容量/内层物品，容量维度正序还是倒序）取决于”能否重复选择同一个物品”——写反了不会报错，只会得到错误答案，务必对着状态转移方程逐项核对循环方向的含义。

121~714 买卖股票系列是同一个状态机的不同约束版本：状态是”今天，是否持有股票（以及冷冻期/交易次数等约束维度）“，转移是”今天的状态由昨天的状态转移而来”——认出这是一个状态机后，122（不限次数）、123/188（限定次数）、309（含冷冻期）、714（含手续费）都只是给状态机加了一个约束维度或一条边的代价，模板不变。

贪心：能证明局部最优可以推出全局最优

55/45-跳跃游戏、134-加油站、763-划分字母区间 不需要存下所有候选，因为可以直接证明”每一步选当前看起来最优的那个，就不会错过全局最优”——45 每步都维护”当前能跳到的最远距离”，贪心地在这个范围内选下一步能跳得更远的位置，不需要枚举所有跳法。

贪心最大的风险是”看起来很像贪心，其实没法证明”——如果想不出”为什么局部最优就是全局最优”的证明或反例，说明它可能其实需要 DP。621-任务调度器 是一个不那么直观的贪心：先安排出现次数最多的任务，其余任务见缝插针填空，结果只取决于最高频次和频次并列的任务数，这个结论本身需要证明而非直觉。

易混：什么时候两者会被放在一起比较

53-最大子数组和 既能贪心（Kadane 算法：当前缀和为负就直接丢弃重新开始）也能 DP（dp[i] = max(dp[i-1], 0) + nums[i]）——这不是巧合，当贪心策略恰好可以写成”只依赖上一步状态”的递推式时，贪心就是 DP 的一个特例（状态只需要保留一个值，不需要保留整个数组）。反过来，如果一道题的贪心策略无法证明，退回去写完整的 DP（保留所有子问题的解）通常总是正确的，只是可能不是最优复杂度。