动态规划核心思想与解题框架：从爬楼梯到背包问题实战解析-育师

1. 从“爬楼梯”到“最优解”：动态规划的直觉建立

如果你刷过LeetCode，或者准备过技术面试，那么“动态规划”这四个字大概率是你绕不开的一座大山。它不像排序、链表那样直观，也不像二叉树那样有固定的遍历模式。很多人第一次接触动态规划（Dynamic Programming，简称DP）时，都会觉得它既神秘又复杂——状态、转移方程、最优子结构、重叠子问题……一堆术语砸下来，直接把人搞懵。

但我想说，动态规划的核心思想，其实非常朴素，甚至可以说是一种“聪明的穷举”。它源于我们解决复杂问题时一种本能的思考方式：记住已经解决过的子问题的答案，避免重复计算。我们从一个最经典的入门题开始，建立这种直觉。

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

最直接的暴力想法是递归：要爬到第n阶，我可以从第n-1阶爬1步上来，也可以从第n-2阶爬2步上来。所以，f(n) = f(n-1) + f(n-2)。这就是状态转移方程的雏形。如果我们直接写递归代码，会发现计算f(5)时需要f(4)和f(3)，计算f(4)又需要f(3)和f(2)……f(3)被重复计算了多次。当n很大时，这种重复是指数级增长的，效率极低。

动态规划在这里做了什么？它说：既然f(3)会被用到很多次，那我们为什么不第一次算出来之后就把它存起来呢？于是我们开一个数组dp，dp[i]表示爬到第i阶楼梯的方法数。我们知道dp[1] = 1（爬1阶），dp[2] = 2（一次爬2阶，或分两次各爬1阶）。那么对于i >= 3，dp[i] = dp[i-1] + dp[i-2]。我们只需要从i=3开始，一路算到i=n，每个dp[i]只计算一次，最后返回dp[n]即可。

这个过程揭示了动态规划的两个核心性质：

最优子结构：问题的最优解可以由其子问题的最优解构造出来。爬到第n阶的最优解（方法总数），由爬到第n-1阶和第n-2阶的最优解（方法总数）推导而来。
重叠子问题：在递归求解过程中，相同的子问题被反复计算。动态规划通过列表（记忆化）避免了这种重复。

所以，动态规划不是什么魔法，它就是一种用空间换时间的策略，通过系统地记录并复用子问题的解，来高效解决具有重叠子问题的优化问题。很多看似复杂的题目，其内核就是这个简单的思想。接下来，我们会拆解动态规划的解题框架，并用不同类型的LeetCode经典题目来填充这个框架，让你不仅知道怎么做，更明白为什么这么做。

2. 动态规划解题的标准化四步框架

理解了核心思想后，我们需要一个可重复、可实践的解题步骤。经过大量题目训练，我总结了一套四步法，几乎适用于所有动态规划问题。这套方法能帮你从一团乱麻中理清头绪。

2.1 第一步：定义状态数组（dp数组）及其含义

这是最关键的一步，直接决定了问题能否被正确解决。状态的定义需要准确描述当前问题的某个“局面”。通常，dp[i]或者dp[i][j]代表的是：在某种限制条件下，考虑到前i个元素（或处于i位置、拥有i容量等）时，我们想要的那个最优值（最大、最小、方法数等）。

关键思考：题目问什么，状态就定义什么。但需要找到那个可以递推的“维度”。

问最大利润：dp[i]可能表示第i天结束时的最大利润。
问能否分割：dp[i]可能表示字符串前i个字符能否被成功分割。
问最长子序列：dp[i]可能表示以第i个元素结尾的某种子序列的最大长度。
涉及两个维度（如字符串比较、背包问题）：dp[i][j]就非常常见，表示考虑第一个序列的前i个元素和第二个序列的前j个元素时的状态。

经验之谈：很多初学者喜欢一上来就想转移方程，这很容易卡住。先静下心来，问自己“我需要用什么信息来描述当前走到哪一步了？我想要的结果如何用这个信息表达出来？” 把状态定义写在注释里，是很好的习惯。

2.2 第二步：推导状态转移方程

这是动态规划的灵魂，也是最考验逻辑思维能力的一步。我们需要找出dp[i]（或dp[i][j]）与之前的状态（通常是dp[i-1]，dp[i-2]，dp[i-1][j-1]等）之间的关系。可以问自己这样一个问题：“要达到当前状态，有哪几种可能的选择（或上一个状态是什么）？每种选择对应的结果是什么？”

回到爬楼梯问题：要达到第i阶，要么从i-1阶走1步，要么从i-2阶走2步。所以dp[i] = dp[i-1] + dp[i-2]。这就是转移方程。

再比如 LeetCode 122. 买卖股票的最佳时机 II（无限交易次数）：定义dp[i][0]表示第i天交易结束后，持有股票的最大利润；dp[i][1]表示第i天交易结束后，不持有股票的最大利润。

对于dp[i][0]：我今天持有股票，要么是昨天就持有，今天没动 (dp[i-1][0])；要么是昨天不持有，今天买入 (dp[i-1][1] - prices[i])。两者取最大值。
对于dp[i][1]：我今天不持有股票，要么是昨天就不持有 (dp[i-1][1])；要么是昨天持有，今天卖出 (dp[i-1][0] + prices[i])。两者取最大值。方程就出来了：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

注意：推导时一定要结合状态定义。dp[i]是“以 i 结尾”还是“考虑前 i 个”，对应的转移方程可能天差地别。

2.3 第三步：确定初始状态（Base Case）

递推需要有起点，否则就会像没有第一块骨牌的多米诺。初始状态是那些不能再被分解的、最基础子问题的解。通常我们需要手动设置dp[0]、dp[1]或者dp[0][j]、dp[i][0]的值。

爬楼梯：dp[1] = 1,dp[2] = 2。注意，这里n从1开始，为了代码健壮性，需要处理n=0或n=1的边界。
背包问题：dp[0][j]表示容量为 j 的包装0件物品，价值自然是0。dp[i][0]表示容量为0的包，能装的价值也是0。
字符串类问题：空字符串往往对应dp[0]，其值需要根据题意确定（比如空串能否匹配等）。

踩坑点：初始状态设置错误会导致整个递推结果全错。务必结合题目含义仔细检查。一个技巧是，在纸上画一个小的、具体的例子，手动推导前几步，来验证你的状态定义、转移方程和初始状态是否自洽。

2.4 第四步：确定遍历顺序与计算最终结果

这一步关乎代码如何正确无误地执行。

遍历顺序：要保证在计算dp[i]时，它所依赖的所有子状态（如dp[i-1],dp[i-2]）都已经被计算并存储好了。对于一维dp，通常是从前向后（如爬楼梯）或从后向前（如完全背包的某些变体）遍历。对于二维dp，要搞清楚i和j的依赖关系，决定是逐行遍历还是逐列遍历，或者斜向遍历。
最终结果：状态定义是什么，最终答案往往就是哪个状态。可能是dp[n]，可能是dp[n-1][m-1]，也可能是整个dp数组中的最大值（如最长递增子序列）。

将这四步套用到任何DP问题上，你的思路会清晰很多。下面，我们就用这个框架，去攻克几类经典的动态规划问题。

3. 线性动态规划：序列上的经典问题

这类问题的状态通常只与序列的前一个或前几个位置相关，是理解DP的基础。

3.1 最长递增子序列（LIS）：LeetCode 300

这是面试中的常客。题目要求找到数组中最长的、严格递增的子序列的长度。

状态定义：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。注意，这里必须是“以 i 结尾”，因为这样我们才能通过连接nums[i]来形成新的子序列。如果定义为“前 i 个元素中的最长子序列长度”，则无法方便地判断能否连接nums[i]。
转移方程：对于每个i，我们需要遍历j从0到i-1。如果nums[i] > nums[j]，说明nums[i]可以接在nums[j]结尾的子序列后面，形成一个更长的递增子序列。因此，dp[i] = max(dp[i], dp[j] + 1)对所有满足nums[i] > nums[j]的j成立。如果没有任何j满足条件，那么dp[i] = 1（子序列只包含自身）。
初始状态：每个位置至少可以以自己为子序列，所以初始时dp[i] = 1。
遍历与结果：外层i从0到n-1遍历，内层j从0到i-1遍历。最终结果不是dp[n-1]，而是整个dp数组中的最大值，因为最长子序列不一定以最后一个元素结尾。

复杂度与优化：上述解法时间复杂度 O(n²)。存在一种利用“耐心排序”思想、结合二分查找的 O(n log n) 优化解法，维护一个“有序的尾部最小元素数组”，这里不展开，但知道有更优解对面试很重要。

3.2 最大子数组和：LeetCode 53

给你一个整数数组nums，请你找出一个具有最大和的连续子数组，返回其最大和。

状态定义：dp[i]表示以nums[i]结尾的连续子数组的最大和。同样，定义成“以 i 结尾”是为了保证子数组的连续性。
转移方程：对于nums[i]，只有两种选择：要么单独成为一个子数组 (nums[i])，要么接在以nums[i-1]结尾的子数组后面 (dp[i-1] + nums[i])。我们要取和最大的那种，所以dp[i] = max(nums[i], dp[i-1] + nums[i])。
初始状态：dp[0] = nums[0]。
遍历与结果：从i=1开始遍历。最终结果是dp数组中的最大值。

空间优化：由于dp[i]只依赖于dp[i-1]，我们可以只用一个变量pre来记录前一个状态，将空间复杂度从 O(n) 降到 O(1)。这是动态规划常见的优化手段。

def maxSubArray(nums): n = len(nums) max_sum = curr_sum = nums[0] for i in range(1, n): # 这里的 curr_sum 就相当于 dp[i-1] # 我们计算新的 curr_sum (即 dp[i]) curr_sum = max(nums[i], curr_sum + nums[i]) # 随时更新全局最大值 max_sum = max(max_sum, curr_sum) return max_sum

3.3 打家劫舍系列：LeetCode 198 & 213

这个系列是理解状态定义的绝佳例子。

LeetCode 198. 打家劫舍：一排房屋，不能偷相邻的两家，求最大收益。

状态定义：dp[i]表示考虑偷前 i 间房屋（不一定偷第 i 间）能获得的最大金额。这是一种常见的定义方式。
转移方程：对于第i间房（下标i-1），有两种选择：
1. 偷它：那么第i-1间不能偷，收益是dp[i-2] + nums[i-1]。
2. 不偷它：那么收益就是dp[i-1]。取最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
初始状态：dp[0] = 0（没有房屋），dp[1] = nums[0]（只有一间房，必偷）。
结果：dp[n]。

LeetCode 213. 打家劫舍 II：房屋围成一圈，其他条件相同。

核心矛盾：首尾相连，偷了第一家就不能偷最后一家。
解题技巧：既然首尾不能同时偷，我们可以把环拆成两个线性问题：
1. 考虑偷第一家，不偷最后一家：计算范围[0, n-2]的最大收益。
2. 考虑不偷第一家，可以偷最后一家：计算范围[1, n-1]的最大收益。最终结果是这两个线性问题结果的最大值。这体现了动态规划中“分类讨论”的思想。

4. 背包问题：从01背包到完全背包

背包问题是动态规划的另一个核心范式，主要解决“选择”与“限制”下的最优组合问题。

4.1 01背包问题：每个物品最多选一次

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

状态定义：最经典的定义是dp[i][j]，表示从前 i 件物品中选择，放入容量为 j 的背包中，可以获取的最大价值。
转移方程：对于第i件物品（实际下标i-1），我们面临选择：
1. 不选：那么最大价值就是dp[i-1][j]，即前i-1件物品在容量j下的最大价值。
2. 选：前提是背包容量j >= weight[i-1]。如果选，那么背包需要预留出weight[i-1]的容量给这个物品，剩下的j - weight[i-1]容量用来装前i-1件物品。总价值为dp[i-1][j - weight[i-1]] + value[i-1]。两者取最大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1])。
初始状态：dp[0][j] = 0（0件物品，价值为0），dp[i][0] = 0（容量为0，价值为0）。
遍历顺序：外层循环遍历物品i从1到N，内层循环遍历背包容量j从1到V。注意：内层循环可以正序也可以倒序，但在空间优化时至关重要。
空间优化（滚动数组）：观察转移方程，dp[i][j]只依赖于dp[i-1][...]，即上一行的数据。因此我们可以将二维数组压缩成一维数组dp[j]。但此时，内层循环必须倒序（从V到weight[i-1]）遍历！原因在于，如果正序遍历，在计算dp[j]时，dp[j - weight[i-1]]可能已经被本轮的更新覆盖了（即变成了“考虑过当前物品”的状态），这就相当于同一件物品被多次选取，违背了01背包“每个物品仅一次”的规则。倒序遍历可以保证dp[j - weight[i-1]]使用的是上一轮（即未考虑当前物品）的状态。

# 01背包 一维dp数组写法 def knapsack_01(N, V, weight, value): dp = [0] * (V + 1) for i in range(N): # 遍历物品 for j in range(V, weight[i] - 1, -1): # 倒序遍历容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) return dp[V]

4.2 完全背包问题：每个物品无限次选取

与01背包的唯一区别是，每种物品有无限件。

状态定义：同上，dp[i][j]。
转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i-1]] + value[i-1])。注意第二个选项是dp[i][j - weight[i-1]]而不是dp[i-1][...]。这是因为即使考虑了前i件物品，我们仍然可以再次选择第i件物品（因为它无限多）。
空间优化与遍历顺序：使用一维数组时，内层循环需要正序遍历容量。这正是因为完全背包允许重复选取，我们需要dp[j - weight[i-1]]是已经考虑过当前物品i的状态。正序遍历恰好能满足这个要求。

# 完全背包 一维dp数组写法 def knapsack_complete(N, V, weight, value): dp = [0] * (V + 1) for i in range(N): # 遍历物品 for j in range(weight[i], V + 1): # 正序遍历容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) return dp[V]

LeetCode上的背包问题：

416. 分割等和子集：可以转化为01背包。背包容量为sum/2，物品重量和价值都是nums[i]，看是否能恰好装满背包。
494. 目标和：可以转化为01背包。需要一点数学推导，找到需要正数的和。
322. 零钱兑换：完全背包问题。背包容量是amount，物品是硬币面额coins，价值是1（硬币个数），求最小价值（最少硬币数）。注意这里是求最小值，初始化和max要改为min。
518. 零钱兑换 II：完全背包问题，但求的是组合数（方法数）。dp[j]表示凑成金额j的组合数。转移方程为dp[j] += dp[j - coin]。

重要心得：遇到背包类问题，先抽象出“容量”和“物品”，然后判断是01背包（每个物品选一次）还是完全背包（物品无限），最后根据问题是求最大价值、能否装满、最少物品数还是组合数，来调整状态定义、初始化和转移方程。

5. 区间与双序列动态规划

这类问题通常涉及两个序列（如字符串）的比较，或者一个序列上的区间操作，状态通常是二维的dp[i][j]。

5.1 最长公共子序列（LCS）：LeetCode 1143

给定两个字符串text1和text2，返回它们的最长公共子序列的长度。

状态定义：dp[i][j]表示text1的前i个字符（[0:i)）和text2的前j个字符（[0:j)）的最长公共子序列长度。通常会让dp数组大小为(m+1) x (n+1)，dp[0][j]和dp[i][0]表示空串。
转移方程：考虑text1[i-1]和text2[j-1]这两个字符。
1. 如果它们相等：那么这个字符一定在LCS中。dp[i][j] = dp[i-1][j-1] + 1。
2. 如果它们不相等：那么LCS不可能同时包含它们。LCS可能来自text1的前i-1和text2的前j个字符，也可能来自text1的前i和text2的前j-1个字符。取最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始状态：dp[0][j] = 0,dp[i][0] = 0。
遍历顺序：两层循环，i从1到m，j从1到n。顺序无关紧要，因为dp[i][j]依赖于其左、上、左上三个方向的状态。
结果：dp[m][n]。

5.2 编辑距离：LeetCode 72

给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数（插入、删除、替换一个字符）。

状态定义：dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作数。
转移方程：考虑对word1[i-1]的操作。
1. 如果word1[i-1] == word2[j-1]：不需要操作，dp[i][j] = dp[i-1][j-1]。
2. 如果不等：我们有三种选择，取最小值：
  - 删除word1[i-1]：操作数 =dp[i-1][j] + 1
  - 插入一个字符到word1（相当于匹配word2[j-1]）：操作数 =dp[i][j-1] + 1
  - 替换word1[i-1]为word2[j-1]：操作数 =dp[i-1][j-1] + 1dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
初始状态：dp[i][0] = i（将i个字符全部删除），dp[0][j] = j（插入j个字符）。
结果：dp[m][n]。

踩坑点：初始状态很容易想错。牢记dp[i][j]的定义是“转换所需步数”，从空串到长度为i的串，自然需要i次插入操作。

5.3 回文子串与子序列

LeetCode 647. 回文子串：计算字符串中回文子串的数目。

状态定义：dp[i][j]表示字符串s的子串[i, j]是否是回文串（布尔值）。
转移方程：首先，如果s[i] != s[j]，肯定不是回文。如果s[i] == s[j]，那么：
1. 如果j - i <= 1（即长度为1或2），肯定是回文。
2. 否则，取决于内部子串[i+1, j-1]是否是回文，即dp[i+1][j-1]。所以dp[i][j] = (s[i] == s[j]) and (j - i <= 1 or dp[i+1][j-1])。
遍历顺序：这里dp[i][j]依赖于dp[i+1][j-1]，即左下方的状态。因此不能简单地i从0到n，j从0到n。需要保证在计算dp[i][j]时，dp[i+1][j-1]已经被计算过了。一种常见的遍历方式是：外层循环枚举子串长度L从1到n，内层循环枚举起点i，从而确定终点j = i + L - 1。
结果：统计所有dp[i][j] == True的个数。

LeetCode 516. 最长回文子序列：求最长回文子序列的长度（子序列不要求连续）。

状态定义：dp[i][j]表示字符串s在区间[i, j]内的最长回文子序列长度。
转移方程：
1. 如果s[i] == s[j]：那么这两个字符可以贡献到回文子序列中，dp[i][j] = dp[i+1][j-1] + 2。
2. 如果s[i] != s[j]：那么这两个字符不可能同时出现在最长回文子序列中。分别考虑去掉s[i]或s[j]的情况，取最大值：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
初始状态：dp[i][i] = 1（单个字符是回文）。
遍历顺序：类似于回文子串，需要从小区间向大区间递推。可以采用长度L从2到n的遍历方式。
结果：dp[0][n-1]。

6. 状态机动态规划：处理复杂状态转移

有些问题的状态不是简单的“选或不选”，而是有多个状态之间相互转换。股票买卖系列是这类问题的典型代表。

我们已经见过LeetCode 122（无限交易），现在看一个更复杂的。

LeetCode 309. 最佳买卖股票时机含冷冻期：卖出股票后，你无法在第二天买入股票（即冷冻期为1天）。

状态定义：我们需要更细致地刻画每天结束时的状态。通常定义三种状态：
1. dp[i][0]: 第i天结束时，持有股票的最大利润。
2. dp[i][1]: 第i天结束时，不持有股票，且处于冷冻期（即今天卖出了股票）。
3. dp[i][2]: 第i天结束时，不持有股票，且不处于冷冻期。
转移方程（思考每个状态昨天可能是什么状态）：
- dp[i][0]（今天持有）：要么昨天就持有 (dp[i-1][0])，要么昨天不持有且非冷冻期，今天买入 (dp[i-1][2] - prices[i])。不能从冷冻期买入，因为冷冻期不能操作。
- dp[i][1]（今天卖出进入冷冻期）：那昨天必须持有股票，然后今天卖出。所以dp[i][1] = dp[i-1][0] + prices[i]。
- dp[i][2]（今天不持有且非冷冻期）：说明今天没有任何操作。那么昨天结束时可能是不持有股票的任何状态（冷冻期或非冷冻期）。所以dp[i][2] = max(dp[i-1][1], dp[i-1][2])。
初始状态：
- dp[0][0] = -prices[0]（第一天买入）
- dp[0][1] = 0（第一天不可能卖出，但可初始化为0，不影响后续）
- dp[0][2] = 0（第一天不操作）
结果：最后一天（第n-1天）结束时，持有股票肯定不是最优的（因为没卖掉），所以结果是max(dp[n-1][1], dp[n-1][2])。

这种“状态机”的思考方式，能将复杂的约束条件（如冷冻期）清晰地建模出来，是解决此类问题的利器。关键在于定义出所有可能的状态，并厘清状态之间如何合法地转换。

7. 路径规划与多维动态规划

这类问题通常在一个矩阵或网格中寻找最优路径，状态与位置(i, j)相关。

LeetCode 62. 不同路径&63. 不同路径 II：机器人从左上角走到右下角，只能向右或向下走，求路径总数。63题增加了障碍物。

状态定义：dp[i][j]表示从起点(0,0)走到(i,j)的路径总数。
转移方程：由于只能向右或向下，所以要走到(i,j)，上一步只可能是从(i-1,j)下来，或者从(i,j-1)过来。所以dp[i][j] = dp[i-1][j] + dp[i][j-1]。
初始状态：对于62题（无障碍），第一行和第一列的所有位置都只有一条路径（一直向右或一直向下），所以dp[0][j] = 1,dp[i][0] = 1。
障碍物处理（63题）：如果(i,j)是障碍物，则dp[i][j] = 0。此外，初始化第一行和第一列时，一旦遇到一个障碍物，后面的位置也都不可达，路径数为0。
遍历顺序：两层循环，i从0到m-1，j从0到n-1。因为dp[i][j]依赖于其上方和左方的状态，这个顺序是合理的。
结果：dp[m-1][n-1]。

LeetCode 64. 最小路径和：在网格中找一条从左上到右下的路径，使得路径上的数字总和最小。

状态定义：dp[i][j]表示从起点(0,0)走到(i,j)的最小路径和。
转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
初始状态：dp[0][0] = grid[0][0]。第一行只能从左来：dp[0][j] = dp[0][j-1] + grid[0][j]。第一列只能从上来：dp[i][0] = dp[i-1][0] + grid[i][0]。
结果：dp[m-1][n-1]。

个人体会：网格类DP是相对直观的，难点往往在于处理边界条件（第一行、第一列）和障碍物。在纸上画一个3x3的小网格，手动推导一下dp数组，能极大地帮助理解初始化和转移过程，避免下标越界等低级错误。

动态规划的世界远不止于此，还有树形DP、状压DP、数位DP等更高级的主题。但掌握以上这些经典模型和四步解题法，足以应对绝大多数面试和竞赛中的DP问题。核心永远是：定义清晰的状态，找到正确的转移，处理好边界，然后优雅地遍历。剩下的，就是通过大量的练习，将这种思维模式内化成本能。当你再看到一道新题，能下意识地去思考“它的状态是什么？怎么转移？”的时候，你就已经跨过动态规划这道坎了。