动态规划核心思想与实战：从斐波那契到背包问题

1. 从“暴力穷举”到“聪明记忆”：动态规划的核心思想

如果你刷过一些算法题，或者准备过技术面试，那么“动态规划”这四个字大概率是你绕不开的一座大山。很多人第一次接触它，感觉就像在看天书：状态转移方程、最优子结构、重叠子问题……一堆术语砸下来，还没开始解题，头已经大了。更让人沮丧的是，看答案时觉得“哦，原来如此简单”，自己动手时却完全不知道从何下手，状态都定义不出来。

我自己在初学动态规划时也经历过这个阶段。后来在大量的项目实战和面试辅导中，我逐渐意识到，动态规划之所以难，不是因为它本身复杂，而是因为大多数教程把它讲复杂了。它本质上是一种用“空间换时间”的编程思想，核心目的就一个：避免重复计算。我们可以从一个最经典的例子——斐波那契数列——来直观感受一下。

斐波那契数列的定义是：F(0)=0， F(1)=1， F(n)=F(n-1)+F(n-2) (n>=2)。如果让你写一个函数计算 F(20)，最直观的写法就是递归：

def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)

这个代码简洁明了，但效率极其低下。如果你画出fib(5)的递归树，你会发现fib(3)被计算了两次，fib(2)被计算了三次。随着 n 增大，这种重复计算是指数级增长的。计算fib(40)可能就需要好几秒甚至更久。这就是典型的“重叠子问题”：在求解大问题的过程中，许多更小的子问题被反复计算。

动态规划的第一招就是“记忆化搜索”（Memoization）。我们开一个数组（或者字典）memo，在计算fib(n)之前，先查一下memo[n]有没有值。如果有，直接返回；如果没有，再计算，并把结果存进memo。这样，每个子问题只会被计算一次。

def fib_memo(n, memo={}): if n <= 1: return n if n not in memo: memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n]

这已经是一种动态规划了（自顶向下）。但更常见的动态规划是“自底向上”的迭代写法。我们直接从最小的子问题开始算起，逐步构建出大问题的解。

def fib_dp(n): if n <= 1: return n # dp[i] 表示斐波那契数列第 i 项的值 dp = [0] * (n + 1) dp[0], dp[1] = 0, 1 # 初始化已知的最小子问题 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] # 状态转移方程 return dp[n]

这个dp数组就是我们“购买”的空间，用它存储了所有子问题的解，从而避免了重复计算。dp[i] = dp[i-1] + dp[i-2]这个式子，就是状态转移方程，它描述了问题状态之间是如何演进的。

所以，动态规划不是什么魔法。当你发现一个问题可以被分解成重叠的子问题，并且子问题的最优解能构成原问题的最优解（最优子结构）时，你就可以尝试用动态规划。它的思考过程可以概括为：定义状态 -> 建立状态转移方程 -> 确定初始（边界）条件 -> 计算顺序（自底向上）-> 输出答案。接下来，我会用几个从易到难的案例，带你完整走一遍这个流程，并分享一些我踩过的坑和总结的技巧。

2. 入门案例拆解：从“爬楼梯”到“零钱兑换”

我们先从两个面试高频题入手，把动态规划的基本流程走通。你会发现，它们的套路是高度一致的。

2.1 爬楼梯问题：理解状态定义

问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

这是最经典的入门题。我们一步步分析：

1. 定义状态：这是最关键的一步，状态定义得好，问题就解决了一半。我们要问自己：什么信息能唯一描述当前所处的“局面”？在这里，“局面”就是你爬到了第几阶，以及到达这一阶有多少种方法。所以，我们定义dp[i]为：爬到第 i 阶楼梯共有多少种不同的方法。这就是我们的“状态”。

2. 建立状态转移方程：思考如何从已知的小状态，推导出未知的大状态。要爬到第 i 阶，最后一步只能从第 i-1 阶爬1步上来，或者从第 i-2 阶爬2步上来。既然到达 i-1 阶有dp[i-1]种方法，到达 i-2 阶有dp[i-2]种方法，并且这些方法互不重复（因为最后一步不同），那么到达第 i 阶的方法总数就是这两者之和。所以方程是：dp[i] = dp[i-1] + dp[i-2]。

3. 确定初始条件：方程需要基础才能启动。dp[1]是多少？爬到第1阶，只有一种方法：爬1步。dp[2]呢？有两种：一次爬2步，或者分两次各爬1步。所以dp[1]=1, dp[2]=2。注意，这里为了方便理解，我们让i从1开始。更常见的写法是定义dp[0]=1（“爬到第0阶”有一种方法：不动），这样dp[1]=1, dp[2]=2也能通过dp[2]=dp[1]+dp[0]推导出来。

4. 计算顺序与实现：显然，我们需要从i=3开始，一直计算到i=n。因为计算dp[i]需要先知道dp[i-1]和dp[i-2]。

def climbStairs(n): if n <= 2: return n dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

空间优化：观察状态转移方程，dp[i]只依赖于前两个状态dp[i-1]和dp[i-2]。我们完全没必要维护整个 O(n) 的数组，只用两个变量滚动更新即可，将空间复杂度降至 O(1)。

def climbStairs_opt(n): if n <= 2: return n prev, curr = 1, 2 # prev 代表 dp[i-2], curr 代表 dp[i-1] for i in range(3, n + 1): # 计算新的 dp[i] new = prev + curr # 滚动更新变量，为下一轮做准备 prev, curr = curr, new return curr # 循环结束时，curr 就是 dp[n]

踩坑心得：很多新手在这里会纠结dp[0]到底该不该等于1。我的建议是，优先从有实际意义的、最小的子问题开始初始化。比如这里从dp[1]和dp[2]开始定义，逻辑更直观，不易出错。如果为了公式统一非要定义dp[0]=1，一定要在注释里写明其物理意义（“不爬”作为一种方案），否则过段时间自己都看不懂。

2.2 零钱兑换问题：理解“选择”与“最值”

问题描述：给你一个整数数组coins，表示不同面额的硬币，以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

这个问题和爬楼梯神似，但加入了“选择”和“求最小值”的概念。我们依然套用流程：

1. 定义状态：dp[i]表示凑出总金额i所需的最少硬币个数。

2. 建立状态转移方程：如何凑出金额i？假设最后一枚硬币的面额是coin，那么在这枚硬币之前，我们已经凑出了金额i - coin，并且使用了dp[i - coin]枚硬币。由于我们要找最少的硬币数，所以我们需要遍历所有可能的coin（前提是coin <= i），选择那个能使dp[i - coin] + 1最小的方案。因此，方程是：dp[i] = min(dp[i - coin] + 1) for coin in coins if coin <= i。

3. 确定初始条件：dp[0] = 0，凑出金额0需要0枚硬币。这是一个合法的、有明确意义的边界状态。对于其他dp[i]，我们初始化为一个很大的数（比如amount + 1或float('inf')），表示“暂时无法凑出”。

4. 计算顺序与实现：我们需要从i=1计算到i=amount。对于每个i，遍历所有硬币面额。

def coinChange(coins, amount): # 初始化 dp 数组，dp[i] 表示凑出金额 i 的最小硬币数 # 初始化为一个不可能的大值，这里用 amount + 1，因为最多用 amount 个1元硬币 dp = [amount + 1] * (amount + 1) dp[0] = 0 # 边界条件 # 遍历所有金额状态 for i in range(1, amount + 1): # 遍历所有硬币选择 for coin in coins: if coin <= i: # 只有硬币面额不大于当前金额时，才能选择 # 状态转移：选择这枚硬币，并取最小值 dp[i] = min(dp[i], dp[i - coin] + 1) # 如果 dp[amount] 没有被更新过，说明无法凑出 return dp[amount] if dp[amount] <= amount else -1

为什么初始化为amount + 1？因为最坏情况是用amount个1元硬币（如果存在1元硬币）。amount + 1是一个有效的“无穷大”标识，最后通过比较dp[amount] > amount来判断是否无解。

实操技巧：在解决求最值（最小/最大）的动态规划问题时，初始化是一个关键。通常做法是：

• 求最小值：初始化为一个很大的正数（如float('inf')或amount+1）。
• 求最大值：初始化为一个很小的数（如float('-inf')或0，具体看情况）。
• 求方案数：通常初始化为0，但dp[0]往往初始化为1（代表一种初始方案）。 务必根据问题的物理意义仔细设定dp[0]，这是整个递推的基石。

3. 二维动态规划进阶：在字符串与矩阵中穿梭

当状态由一个变量无法描述时，我们就需要升维，使用二维甚至更高维的dp数组。字符串匹配和矩阵路径是两类典型问题。

3.1 最长公共子序列：经典的双序列匹配模型

问题描述：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列（LCS）的长度。子序列是指在不改变字符相对顺序的情况下，删除某些字符（也可以不删除）后形成的新字符串。

例如，text1 = "abcde",text2 = "ace"，LCS 是"ace"，长度为3。

1. 定义状态：我们需要同时考虑两个字符串的进度。定义dp[i][j]为：text1的前i个字符和**text2的前j个字符**的最长公共子序列长度。这里“前 i 个”通常指下标从0到 i-1 的子串。这种定义方式非常普遍。

2. 建立状态转移方程：我们比较text1[i-1]和text2[j-1]（因为下标从0开始）。

   • 如果它们相等：那么这个字符一定在LCS中。dp[i][j] = dp[i-1][j-1] + 1。
   • 如果它们不相等：那么这个字符不可能同时出现在LCS中。LCS的长度要么来自text1的前 i-1 个和text2的前 j 个（dp[i-1][j]），要么来自text1的前 i 个和text2的前 j-1 个（dp[i][j-1]）。我们取最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

3. 确定初始条件：当其中一个字符串为空时，LCS长度为0。即dp[0][j] = 0对所有 j，以及dp[i][0] = 0对所有 i。

4. 计算顺序与实现：我们需要一个双重循环，i从 1 到len(text1)，j从 1 到len(text2)。计算dp[i][j]需要其左方、上方、左上方三个状态，这个计算顺序（从左到右，从上到下）是满足的。

def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) # 创建 (m+1) x (n+1) 的二维数组，多出来的一行一列用于表示空串 dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): 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]) return dp[m][n]

如何输出具体的LCS字符串？上述代码只返回了长度。要输出序列，我们需要在填表的同时记录状态转移的方向，然后从dp[m][n]反向回溯。这是一个常见的 follow-up 问题。

经验之谈：二维DP的索引设计是个易错点。dp[i][j]对应text1[0..i-1]和text2[0..j-1]，这样dp[0][*]和dp[*][0]就自然地代表了空串，简化了边界处理。我强烈建议统一使用这种“长度+1”的定义方式，它比直接使用字符串下标（dp[i][j]对应text1[0..i]和text2[0..j]）更不容易出错，因为后者需要单独初始化第一行和第一列。

3.2 最小路径和：在网格中做决策

问题描述：给定一个包含非负整数的m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

1. 定义状态：dp[i][j]表示从左上角(0, 0)走到位置(i, j)的最小路径和。

2. 建立状态转移方程：要走到(i, j)，上一步只能来自其上方(i-1, j)或者左方(i, j-1)。我们选择路径和更小的那条路过来，再加上当前格子的值。因此：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

3. 确定初始条件：

   • 起点：dp[0][0] = grid[0][0]。
   • 第一行（i=0）：只能从左方来，所以dp[0][j] = dp[0][j-1] + grid[0][j]。
   • 第一列（j=0）：只能从上方来，所以dp[i][0] = dp[i-1][0] + grid[i][0]。

4. 计算顺序与实现：双重循环，遍历整个网格即可。由于计算dp[i][j]只需要其上方和左方的值，我们也可以进行空间优化，只维护一维数组。

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] # 初始化起点 dp[0][0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 初始化第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 填充其余部分 for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[m-1][n-1]

空间优化（滚动数组）：

def minPathSum_opt(grid): m, n = len(grid), len(grid[0]) # 只维护一行数据 dp = [0] * n dp[0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] # 处理后续行 for i in range(1, m): # 每行的第一个元素只能从上方来 dp[0] = dp[0] + grid[i][0] for j in range(1, n): # dp[j] 在更新前代表上一行的 dp[i-1][j] # dp[j-1] 代表本行已经计算好的 dp[i][j-1] dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[n-1]

优化后，空间复杂度从 O(m*n) 降到了 O(n)。理解这个优化需要对dp数组在每一轮循环中的含义有清晰的认识。

4. 背包问题精讲：掌握动态规划的经典范式

背包问题是动态规划领域的一座里程碑，它抽象出了一大类“选择-容量-价值”的优化问题。彻底理解背包问题，很多其他问题都能迎刃而解。

4.1 0-1背包问题：每个物品只能选一次

问题描述：有N件物品和一个容量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。

这是最基础的背包模型。关键在于每件物品只能选择0次（不放入）或 1次（放入）。

1. 定义状态：dp[i][j]表示考虑前 i 件物品，在背包容量为j的情况下，可以装入的最大价值。

2. 建立状态转移方程：对于第i件物品（注意i从1开始计数，对应weight[i-1]和value[i-1]），我们有两种选择：

   • 不放入背包：那么最大价值就等于考虑前i-1件物品、容量为j时的最大价值，即dp[i-1][j]。
   • 放入背包（前提是j >= weight[i-1]）：那么最大价值等于“第i件物品的价值”加上“考虑前i-1件物品、剩余容量为j - weight[i-1]时的最大价值”，即value[i-1] + dp[i-1][j - weight[i-1]]。 我们要取这两种选择中的最大值。所以：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1])，其中后一项仅在j >= weight[i-1]时有效。

3. 确定初始条件：当物品数量为0或背包容量为0时，最大价值为0。即dp[0][j] = 0,dp[i][0] = 0。

4. 实现与空间优化：

def knapsack_01(W, weight, value): N = len(weight) dp = [[0] * (W + 1) for _ in range(N + 1)] for i in range(1, N + 1): w_i, v_i = weight[i-1], value[i-1] for j in range(1, W + 1): # 默认不选第 i 件物品 dp[i][j] = dp[i-1][j] # 如果背包容量够，尝试选择第 i 件物品 if j >= w_i: dp[i][j] = max(dp[i][j], dp[i-1][j - w_i] + v_i) return dp[N][W]

观察状态转移方程，dp[i][j]只依赖于dp[i-1][...]，即上一行的数据。因此我们可以将二维数组压缩成一维数组，但需要逆序遍历背包容量j。

def knapsack_01_opt(W, weight, value): N = len(weight) dp = [0] * (W + 1) # dp[j] 表示容量为 j 的背包能装的最大价值 for i in range(N): w_i, v_i = weight[i], value[i] # 必须逆序遍历！保证 dp[j - w_i] 是上一轮（i-1）的结果 for j in range(W, w_i - 1, -1): dp[j] = max(dp[j], dp[j - w_i] + v_i) return dp[W]

为什么必须逆序？因为dp[j - w_i]需要是“未考虑当前物品i”时的值。如果正序遍历，在计算dp[j]时，dp[j - w_i]可能已经被本轮的更新覆盖了（即已经考虑了物品i），这就变成了“完全背包”问题（物品可重复选取），违反了0-1背包的规则。这是背包问题最核心的一个技巧，务必理解。

4.2 完全背包问题：物品数量无限

问题描述：与0-1背包类似，但每种物品有无限件。

状态定义不变，依然是dp[i][j]。状态转移方程需要改变：因为物品i可以选0件、1件、2件……直到放不下。dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i-1]] + value[i-1])， 其中后一项在j >= weight[i-1]时有效。

注意第二个项是dp[i][j - w_i]而不是dp[i-1][j - w_i]。这是因为即使考虑了前i种物品，我们仍然可以再次选择物品i。

一维优化后的代码与0-1背包几乎一样，唯一的区别就是内层循环正序遍历j：

def knapsack_complete(W, weight, value): N = len(weight) dp = [0] * (W + 1) for i in range(N): w_i, v_i = weight[i], value[i] # 完全背包：正序遍历！ for j in range(w_i, W + 1): dp[j] = max(dp[j], dp[j - w_i] + v_i) return dp[W]

正序保证了dp[j - w_i]是已经考虑过当前物品i的结果，从而实现了物品的无限次选取。

核心对比记忆：

• 0-1背包：一维数组优化，内层容量循环逆序(for j in range(W, w_i-1, -1))。
• 完全背包：一维数组优化，内层容量循环正序(for j in range(w_i, W+1))。 这个区别源于状态转移方程中依赖的是上一行(i-1)还是本行(i)的数据。死记硬背容易忘，理解其背后的“依赖关系”才是关键。

5. 状态压缩与降维打击：当空间成为瓶颈

在动态规划中，尤其是二维DP，空间复杂度有时会成为问题（比如网格非常大）。状态压缩技巧（或称滚动数组）可以极大地节省空间。我们之前已经在“爬楼梯”和“最小路径和”中见过一维优化的例子。这里再深入探讨一个更复杂的案例：买卖股票的最佳时机（含冷冻期）。

问题描述：给定一个整数数组prices，其中第i个元素代表了第i天的股票价格。你可以尽可能地完成更多的交易（多次买卖一支股票），但卖出股票后，你无法在第二天买入股票（即冷冻期为1天）。计算你所能获取的最大利润。

这个问题有多个状态：持有股票、不持有股票（且处于冷冻期）、不持有股票（不处于冷冻期）。一个直观的二维DP定义是：

• dp[i][0]: 第i天结束时，持有股票的最大利润。
• dp[i][1]: 第i天结束时，不持有股票，且处于冷冻期（即第i天卖出了股票）的最大利润。
• dp[i][2]: 第i天结束时，不持有股票，且不处于冷冻期的最大利润。

状态转移方程如下：

1. dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])。今天持有股票：要么是昨天就持有，要么是昨天不持有且非冷冻期，今天买入。
2. dp[i][1] = dp[i-1][0] + prices[i]。今天处于冷冻期，意味着今天卖出了股票，所以利润是昨天持有的利润加上今天卖出的收入。
3. dp[i][2] = max(dp[i-1][1], dp[i-1][2])。今天不持有且非冷冻期：要么昨天是冷冻期，要么昨天也是非冷冻期。

初始化：dp[0][0] = -prices[0]（第一天买入），dp[0][1] = 0，dp[0][2] = 0。

这个解法需要 O(n) 的空间（n为天数）。但观察方程，dp[i]只依赖于dp[i-1]。因此我们可以只用三个变量来滚动更新。

def maxProfit_with_cooldown(prices): if not prices: return 0 n = len(prices) # 初始化第0天的状态 hold = -prices[0] # dp[0][0] cold = 0 # dp[0][1] not_hold = 0 # dp[0][2] for i in range(1, n): # 计算第i天的新状态，需要用到旧状态，所以先存下来 pre_hold, pre_cold, pre_not_hold = hold, cold, not_hold # 更新第i天的状态 hold = max(pre_hold, pre_not_hold - prices[i]) cold = pre_hold + prices[i] not_hold = max(pre_cold, pre_not_hold) # 最后一天，持有股票肯定不是最优（没卖掉），所以取 cold 和 not_hold 的最大值 return max(cold, not_hold)

这种优化将空间复杂度从 O(n) 降到了 O(1)。关键在于识别出状态转移只依赖于前一个时间步的状态，并且注意在更新时，由于变量会相互覆盖，需要先用临时变量保存旧值。

降维的通用思路：当你发现dp[i][...]的状态只依赖于dp[i-1][...]或有限的前几个状态时，就可以考虑用滚动数组。具体做法是：

1. 分析状态转移方程，确定依赖关系。
2. 如果只依赖上一行，通常可以压缩到一维（如0-1背包）或几个变量（如股票问题）。
3. 如果依赖前两行，可以压缩到两行交替使用。
4. 特别注意更新顺序：在压缩到一维时，逆序还是正序遍历容量/天数，取决于依赖的是“旧状态”还是“可能被覆盖的新状态”。这是最容易出错的地方，画个图模拟一下更新过程会很有帮助。

6. 动态规划的“灵魂”：如何识别与构造状态转移方程

学了一堆例题，但遇到新题还是不会，这是常态。动态规划的难点不在于编码，而在于“如何想到用DP”以及“如何定义状态和方程”。我总结了一套思考框架，亲测有效。

第一步：判断问题是否具有“最优子结构”和“重叠子问题”。

• 最优子结构：一个问题的最优解包含其子问题的最优解。比如最短路径问题，从A到C的最短路径如果经过B，那么这条路径上从A到B、从B到C的段落也必定分别是A到B、B到C的最短路径。
• 重叠子问题：在递归求解时，相同的子问题会被反复计算。可以通过画递归树或心算来感受。如果感觉“暴力搜索会做很多重复工作”，那大概率可以用DP优化。

第二步：尝试定义状态。状态就是描述问题某个“局面”的一组参数。问自己：需要哪些信息，才能唯一确定当前所处的阶段，并且能够向后续阶段推进？

• 单序列问题（如最大子数组和）：通常状态定义为dp[i]，表示以第i个元素结尾的某种性质。
• 双序列问题（如编辑距离、LCS）：通常状态定义为dp[i][j]，表示涉及第一个序列的前i个和第二个序列的前j个。
• 背包问题：状态是dp[i][j]，i表示物品范围，j表示容量限制。
• 区间问题（如石子合并）：状态可能是dp[i][j]，表示区间[i, j]上的最优解。
• 状态机问题（如股票买卖）：状态需要多个维度，如dp[i][0/1/2]表示第i天处于不同状态（持有、卖出、冷冻）下的最优解。

一个技巧：先想想暴力递归怎么做。递归函数的参数通常就是状态变量。

第三步：推导状态转移方程。这是最核心的一步。思考：如何从已知的、更小的状态，计算出当前状态？通常对应着在当前位置做一个“决策”。

• 对于dp[i]：看看它和dp[i-1]，dp[i-2]... 有什么关系。决策点往往是“是否包含当前元素”、“从哪个前驱状态转移过来”。
• 对于dp[i][j]：看看它和dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]有什么关系。决策点往往是“两个序列的当前元素是否匹配”、“进行哪种操作（增删改）”。
• 通用形式：dp[新状态] = BestChoice( dp[所有可能的前驱状态] + 本次决策的代价/收益 )。这里的BestChoice可能是min,max,sum等。

第四步：确定边界条件（Base Case）。也就是最小的、不可再分的子问题的解。通常是状态索引为0或1时的值。一定要给这些初始状态赋予有实际意义的、正确的值，这是递推的起点。

第五步：确定计算顺序。要保证在计算dp[当前状态]时，它所依赖的所有子状态都已经被计算出来。对于一维DP，通常是从左到右；对于二维DP，通常是从上到下、从左到右。有时也可能需要斜着遍历或者从后往前遍历。

第六步：实现并考虑优化。先写出清晰但可能费空间的版本（比如完整的二维数组）。确保正确后，再考虑是否可以进行状态压缩（滚动数组）、空间优化等。

7. 避坑指南与实战心得

在多年的刷题和项目应用中，我积累了一些动态规划中常见的“坑”，希望能帮你少走弯路。

坑一：状态定义不当，导致转移方程复杂或错误。这是最常见的问题。好的状态定义应该让转移方程简洁自然。如果发现方程写起来非常别扭，或者需要很多if-else分支，很可能状态定义需要调整。例如在“最长递增子序列”问题中，定义dp[i]为“以nums[i]结尾的最长递增子序列长度”，比定义为“前i个元素的最长递增子序列长度”要容易推导得多，因为后者无法仅通过dp[i-1]确定dp[i]。

坑二：忽视边界条件，或初始化错误。dp[0]、dp[0][0]这些初始值必须仔细推敲。例如在“不同路径”问题中，dp[0][j]和dp[i][0]都应该初始化为1，因为到第一行或第一列的任意格子都只有一条路径。如果初始化成0，结果就全错了。一个检查方法是：用最小的、能手动验证的实例（比如2x2网格）跑一遍你的DP初始化，看结果是否正确。

坑三：遍历顺序错误，导致依赖的子状态还未计算。尤其是在进行空间优化（如一维数组）时，遍历顺序至关重要。0-1背包的内层逆序和完全背包的内层正序就是典型例子。我的建议是：先写出二维的、逻辑清晰的版本，然后像我们前面做的那样，在纸上画出一维数组，模拟更新过程，来确定正确的遍历顺序。

坑四：混淆“子序列”和“子数组”。这是两个完全不同的概念。“子序列”可以不连续，而“子数组”必须是连续的。它们对应的DP状态定义和转移方程天差地别。例如“最大子数组和”问题，dp[i]定义必须以nums[i]结尾，因为子数组要求连续；而“最长递增子序列”问题，dp[i]虽然也以nums[i]结尾，但转移时需要遍历前面所有的j，因为子序列不要求连续。

坑五：过度追求一维优化，牺牲了代码可读性。在面试或项目初期，正确性远比那一点空间优化重要。除非空间限制非常严格，否则我建议先写出直观的二维DP代码，确保逻辑正确、面试官能看懂。在解释清楚思路后，如果时间允许，再提一句“这个还可以用滚动数组优化到O(n)空间”。一上来就写优化后的代码，容易把自己绕进去，也容易让面试官困惑。

实战心得：从“记忆化搜索”入手如果你觉得直接想状态转移方程很困难，可以尝试先写“记忆化搜索”（Memoization），也就是带缓存的递归。这更符合人类的自然思维（自顶向下）。写出递归函数后，其参数就是状态，递归调用就是状态转移。然后很容易就能改写成自底向上的迭代DP。这是一个非常有效的训练方法。

最后，动态规划是一种需要大量练习才能内化的思想。不要指望看几篇文章就能精通。我的建议是，按照专题（线性DP、区间DP、背包DP、状态机DP等）集中刷题，每做一题，不仅写出代码，更要能在白板上清晰地讲出状态定义、方程推导、边界条件和优化思路。当你拿到新题，能下意识地开始“定义状态 -> 找转移 -> 定边界”时，你就真正入门了。剩下的，就是在不断的实践中，积累更多模型和技巧，让这种思维成为你的本能。