1. 核心思想：记忆化地解决重叠子问题

想象一下你要计算斐波那契数列的第10项 fib(10)。 一个天真的递归方法是 fib(n) = fib(n-1) + fib(n-2)。

如果你画出计算 fib(5) 的递归树，你会发现：

• 为了算 fib(5)，你需要 fib(4) 和 fib(3)。
• 为了算 fib(4)，你需要 fib(3) 和 fib(2)。
• …等等。

你会注意到 fib(3) 被计算了两次，fib(2) 被计算了三次… 随着 n 的增大，这种重复计算会呈指数级增长。

动态规划的核心思想就是为了解决这个问题而生的。 它可以概括为：

将一个复杂的大问题，分解成一系列规模更小的、相互重叠的子问题。先求解这些子问题，并将它们的结果存储起来（记忆化），以便在后续求解更大的问题时，可以直接使用这些已经算好的结果，从而避免大量的重复计算。

我们可以用一个简单的比喻来理解： 做饭与备菜

• 普通递归：就像一个没有计划的厨师。每次需要用到“切好的洋葱”时，他都重新拿一个新洋葱从头开始切。如果一道菜需要用到三次“切好的洋葱”，他就切三次。
• 动态规划：就像一个有经验的厨师。他会提前“备菜”。他会一次性把所有需要的洋葱都切好，放在一个盘子里。之后任何时候需要“切好的洋葱”，他都直接从盘子里拿。这个“盘子”就是DP中的 “备忘录”或“dp表”。

2. 动态规划的“两大支柱”：适用条件

不是所有问题都适合用动态规划来解决。一个问题必须具备以下两个基本性质，才能称得上是“动态规划问题”。

a) 最优子结构 (Optimal Substructure)

一个问题的最优解，包含了其子问题的最优解。

这意味着，我们可以通过组合子问题的最优解，来构造出原问题的最优解。

• 例子：最短路径问题
  • 从城市A到城市C的最短路径，如果必须经过城市B，那么这条路径必然由“从A到B的最短路径”和“从B到C的最短路径”两部分组成。
  • 如果A到B的部分不是最短的，那么我总可以换成一条更短的A->B路径，从而使整个A->C的路径也变得更短，这就与“原路径是最短的”相矛盾。

最优子结构是DP能够“分而治之”的根本保证。

b) 重叠子问题 (Overlapping Subproblems)

在递归求解的过程中，许多子问题会被反复计算多次。

这是DP能够提升效率的关键。如果子问题都是独立的，互不重叠（例如归并排序的子问题），那么用分治法就足够了，DP的“记忆化”就失去了意义。

• 例子：斐波那契数列
  • 如前所述，fib(3)、fib(2)等子问题在递归树中被多次调用，这就是典型的重叠子问题。

DP正是通过“查表”来消除这些冗余计算，将指数级的时间复杂度优化为多项式级别。

3. DP解题的“四步曲”：设计方法论

掌握了思想，我们还需要一套行之有效的方法论来解决具体的DP问题。这套“四步曲”可以帮助你清晰地构建出DP解法。

第一步：定义状态 (State) - 这是最关键的一步

你需要创建一个数组（通常称为 dp 数组或 dp 表），并明确其中每个元素的含义。状态定义必须是清晰、无歧义的，并且能涵盖问题的所有子问题。

• 一维DP：dp[i] 可能表示“处理到第 i 个元素时的最优解”、“凑成金额 i 的方法数”等等。
• 二维DP：dp[i][j] 可能表示“使用前 i 个物品，在容量为 j 的情况下的最优解”、“字符串 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度”等等。

问自己：dp[i] 到底代表什么？ 把它的含义用一句话写下来。如果做不到，说明你的状态定义很可能是有问题的。

第二步：找出状态转移方程 (Function) - 这是算法的核心

状态转移方程是一个递推关系式，它描述了问题的不同状态之间是如何关联的。它说明了如何通过一个或多个较小子问题的解，来计算出更大问题的解。

• 形式：dp[i] = f(dp[i-1], dp[i-2], ...)
• 思考方式：思考 dp[i] 的值是如何从之前的状态（如 dp[i-1]）推导出来的。为了得到 dp[i] 的解，最后一步可以做什么决策？这些决策会依赖哪些之前的状态？

例如，在0-1背包问题中，对于 dp[i][j]，你的决策只有两种：

1. 不放第 i 个物品：那么最大价值就等于只用前 i-1 个物品在容量 j 下的最大价值，即 dp[i-1][j]。
2. 放第 i 个物品：那么价值就是 v[i] 加上“用前 i-1 个物品在剩余容量 j - w[i] 下的最大价值”，即 v[i] + dp[i-1][j-w[i]]。 状态转移方程就是在这两者中取最大值。

第三步：初始化 (Initialization) - 这是递推的起点

你需要为 dp 数组设置初始值或边界条件。这些是递推公式无法计算，但又是整个递推过程开始所必需的“已知条件”。

• 例如，dp[0] 的值，或者 dp 表的第一行和第一列的值。
• 如果初始化错误，整个递推过程都会出错，所谓“差之毫厘，谬以千里”。

第四步：确定计算顺序 (Order) - 这是执行的蓝图

根据状态转移方程，确定 dp 数组的填充顺序。通常是自底向上 (Bottom-Up) 的。

• 原则：当你计算 dp[i] 时，它所依赖的所有状态（如 dp[i-1]）都必须是已经计算出来的。
• 实现：通常通过一个或多个 for 循环来迭代地填充 dp 数组。

4. DP 与其他算法思想的对比

备忘录法 vs. 自底向上DP

• 备忘录法 (Memoization)：是“懒惰的”，只有当一个子问题需要被计算时才去计算它。实现上是递归+一个 cache 数组。
• 自底向上DP (Tabulation)：是“勤奋的”，它会主动计算所有子问题的解，不管后续用不用得到。实现上是循环+一个 dp 数组。

两者在时间复杂度上通常是相同的，但自底向上的DP通常有更小的常数开销（没有递归调用的开销）。