什么是动态规划？动态规划的解题步骤和适用条件是什么？

简化版

动态规划（DP）是把一个大问题拆成互相重叠的子问题，每个子问题只算一次、把结果存起来，用它们递推出更大问题的答案。它能用的两个前提是最优子结构（大问题的最优解由子问题的最优解拼成）和无后效性（一个状态定下来后，怎么到达它的过程不影响后续）。解题固定五步：定义状态 → 写转移方程 → 初始化 → 定遍历顺序 → 取答案。和分治的区别在于：分治的子问题独立、DP 的子问题重叠（所以要记忆化）。

详细版

解 DP 的五步法：

1. 定义状态（dp 数组的含义）：dp[i] 或 dp[i][j] 到底代表什么——这是最关键、最难的一步。
2. 推转移方程：dp[i] 怎么由更小的状态（dp[i-1]、dp[i-2]…）算出来。
3. 初始化：确定边界/起始状态的值（dp[0] 等），错了会全盘皆错。
4. 确定遍历顺序：保证算 dp[i] 时它依赖的状态都已经算好。
5. 取答案：答案是 dp[n]？还是 max(dp[i])？想清楚。

两个适用前提：

• 最优子结构：原问题的最优解，能由子问题的最优解组合而来。
• 无后效性：某状态一旦确定，「如何走到这个状态」的细节不再影响之后的决策——只认状态值本身。

两种实现方式：

• 自顶向下（记忆化搜索）：递归 + 一个备忘录数组，算过的子问题直接查表。
• 自底向上（递推）：从最小子问题开始，用循环一步步填满 dp 数组。

完整版教学

一、动态规划是什么：带记忆的递推

很多问题能写成递归：大问题 = 若干小问题的组合。但如果小问题被反复用到，纯递归会指数级重复计算。最典型的是斐波那契 f(n)=f(n-1)+f(n-2)——f(n-2) 会被 f(n) 和 f(n-1) 都算一遍，递归树里同一个子问题出现无数次。

动态规划的核心动作就是：把每个子问题的答案算一次、存下来，下次直接取。 这样把指数级的重复计算压成线性/多项式。所以一句话抓本质——动态规划 = 递推 + 记忆化（不重复算重叠子问题）。

二、DP 的两个前提：最优子结构 + 无后效性

不是所有问题都能 DP，必须满足两条：

• 最优子结构：大问题的最优解，可以由它的子问题的最优解推出。比如「前 i 个数的最优解」能由「前 i-1 个数的最优解」加上第 i 个数的决策得到。如果子问题的最优解拼不出原问题最优解，DP 就不成立。
• 无后效性：当我们把某个「状态」定下来后，到达这个状态之前走过的具体路径，不影响未来的决策——未来只依赖当前状态的值。正是无后效性，让我们能用一个 dp[i] 概括「所有到达 i 的历史」，而不必记住怎么来的。

无后效性是状态定义的隐形约束：如果发现「同一个 dp[i] 值，后续却会因为历史不同而不同」，说明状态没定对，要把更多信息塞进状态里。

三、解 DP 五步法

拿到一道 DP，按固定套路走：

1. 定义状态：先问「dp[i] 代表什么」。这一步定错，后面全错。状态定义要满足无后效性，且能覆盖答案。
2. 转移方程：分析 dp[i] 能从哪些更小的状态转移过来，写成递推式。这一步的关键是枚举最后一步的决策（第 i 个物品选不选、最后一段怎么切）。
3. 初始化：把递推起点（dp[0]、第一行第一列等）的值定对。边界值往往要结合「状态定义」反推，别拍脑袋。
4. 遍历顺序：保证计算 dp[i] 时，它依赖的所有状态都已经算好（比如背包一维数组要倒序、二维要按行列递增）。
5. 取答案：明确最终答案在 dp 数组的哪个位置——是 dp[n]，还是所有 dp[i] 的最大值。

四、自顶向下 vs 自底向上

同一个 DP 有两种写法：

• 自顶向下 · 记忆化搜索：保留递归的写法，但加一个 memo 数组。进入递归先查 memo，算过就直接返回；没算过就递归求解并存进 memo。思路直观（就是加了缓存的暴力递归），适合状态转移复杂、不好确定遍历顺序的题。
• 自底向上 · 递推：用循环从最小子问题往上填 dp 表。没有递归开销、常数更小、便于状态压缩，是竞赛和面试的主流写法。

两者时间复杂度相同，差别在写法和常数。能想清楚递推顺序就用自底向上；顺序绕就用记忆化搜索。

五、DP vs 分治 vs 贪心

三者经常放一起辨析：

	子问题关系	决策	典型
分治	子问题独立、不重叠	无需回看	归并、快排
动态规划	子问题重叠（要记忆化）	保留所有可能、最后取最优	背包、LCS、编辑距离
贪心	每步只看局部	每步选当前最优、不回头	区间调度、霍夫曼编码

• DP vs 分治：都拆子问题，但分治的子问题独立（算完不再需要），DP 的子问题重叠（同一个被反复要），所以 DP 要存表。
• DP vs 贪心：贪心每步做「当前看起来最好」的选择且不反悔，只有具备「贪心选择性质」时才对；DP 会保留多种可能、最后统一比较，更通用但更慢。贪心对的题 DP 一定对，反之不然。

六、状态压缩：省空间

DP 的空间常能优化。观察转移方程，如果 dp[i] 只依赖前面固定几个状态（如 dp[i-1]、dp[i-2]），就不必存整个数组，用几个变量滚动即可，空间从 O(n) 降到 O(1)（爬楼梯、打家劫舍）。二维 DP 若 dp[i][j] 只依赖上一行，可压成一维滚动数组（背包）。状态压缩不改变时间复杂度，只省空间，是 DP 的常见收尾优化。

七、状态语义、转移来源与遍历顺序

本题状态的完整含义是：状态必须压缩“未来决策所需的全部历史”，相同状态之后的最优结果与到达路径无关。

转移过程是：先定义 dp 的语义和有效范围，再从最后一步枚举前驱；依赖关系决定初始化与遍历方向。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：斐波那契若直接递归会重复计算 F(3)、F(2)，记忆化后每个 n 只求一次，指数树降为 O(n)。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

八、初始化、空间压缩与适用边界

实现边界是：无后效性不是“完全没有历史”，而是历史已经被状态充分概括；状态遗漏会让转移错误，状态过多则复杂度爆炸。

核对项	本题答案
复杂度	状态数 × 每状态转移数；空间可在依赖局部时压缩
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

九、常见误区与追问

• 误区：写出递推式就完成了动态规划。 还要定义状态语义、初值、遍历顺序与答案位置。
• 误区：DP 一定比递归高级。 记忆化递归也是 DP，自底向上只是另一种求值顺序。
• 误区：状态越详细越安全。 冗余维度会增加复杂度，关键是恰好保留未来所需信息。
• 追问：怎样发现状态转移？ 从最后一步倒推：当前答案可能由哪些更小状态产生。
• 追问：何时不能直接用 DP？ 状态无法刻画、无后效性不成立或状态空间不可承受时。
• 追问：如何验证遍历顺序？ 每次计算 dp[s] 前，它依赖的所有状态必须已经可用。

十、加强记忆

动态规划 = 递推 + 记忆化（重叠子问题只算一次）。两个前提：最优子结构（大解由子解拼成）+ 无后效性（状态定了就不管怎么来的）。解题五步：定义状态 → 转移方程（枚举最后一步决策）→ 初始化 → 遍历顺序 → 取答案。实现分自顶向下记忆化搜索和自底向上递推。和分治的分界是「子问题是否重叠」，和贪心的分界是「是否保留多种可能再取最优」。空间常可用滚动数组压缩。