1. 为什么我要从零写一套动态规划拆解

动态规划这四个字，几乎是每个学算法的人绕不过去的一道坎。我见过太多人在面试前突击背几道背包问题、最长公共子序列的模板，结果题目稍微换个皮就完全没思路。也见过有人刷了两百道DP题，遇到新题还是只能干瞪眼。问题出在哪？不是题刷得不够多，而是从一开始就没有建立起对动态规划这门“手艺”的正确认知。

我自己当年学DP也走过弯路。最早接触的是斐波那契数列的递推写法，觉得不过如此；后来碰到零钱兑换、编辑距离，开始觉得有点意思；再往后遇到状态压缩、区间DP、树形DP，整个人就懵了。真正让我开窍的，不是又刷了多少题，而是有一天我突然想明白了一件事：动态规划本质上不是一种算法，而是一种思考问题的方式——它教你怎么把一个大麻烦拆成一串小麻烦，然后从小麻烦的答案里拼出大麻烦的答案。

这套拆解我打算分几篇来写，这是第一篇，重点解决三个问题：动态规划到底在干什么、怎么判断一道题能不能用DP、以及最核心的——状态和转移方程到底怎么设计。我不会一上来就甩一堆数学公式，而是用最直白的话和大量例子，把每个概念揉碎了讲。适合谁看？如果你正在学算法、准备面试、或者单纯想搞明白这个被说烂了却总也学不透的东西，那这篇内容就是写给你的。哪怕你之前完全没接触过DP，只要会写最基本的循环和递归，就能跟上。

2. 动态规划到底在解决什么问题

2.1 从一个最朴素的例子说起

假设你要爬一个n级的楼梯，每次只能走1级或者2级，问一共有多少种走法。这个问题太经典了，经典到很多人一看到就知道答案是斐波那契数列。但我想让你关注的是思考过程，而不是答案本身。

当你站在第n级台阶上往回看，你最后一步是怎么上来的？要么是从第n-1级走1级上来的，要么是从第n-2级走2级上来的。没有第三种可能。所以走到第n级的走法总数，就等于走到第n-1级的走法数加上走到第n-2级的走法数。写成式子就是f(n) = f(n-1) + f(n-2)。

这个式子就是所谓的“状态转移方程”。而f(n)就是“状态”，它表示走到第n级台阶的走法总数。你看，动态规划的核心思想在这里已经体现得淋漓尽致了：当前问题的答案，可以由若干个更小规模的同类问题的答案推导出来。

那为什么不能直接用递归算？因为递归会把同一个子问题重复计算无数次。算f(5)需要f(4)和f(3)，算f(4)又需要f(3)和f(2)，f(3)被算了两次。n稍微大一点，计算量就爆炸了。动态规划的解决办法就是：把每个子问题的答案记下来，用的时候直接查表，不重复算。这就是“记忆化”或者“填表”的思想。

2.2 动态规划与分治、贪心的本质区别

很多人分不清动态规划、分治法、贪心算法。它们确实有相似之处，都是把大问题拆成小问题，但拆的方式和合并的方式完全不同。

分治法是把问题拆成若干个互不重叠的子问题，分别求解后再合并。比如归并排序，左半边和右半边完全独立，排好之后一合并就完事。子问题之间没有交集，所以不需要记录中间结果。

贪心算法是每一步都选当前看起来最优的，期望最终得到全局最优。它不管子问题之间有没有重叠，也不回头检查之前的选择。贪心能用的前提是问题具有“贪心选择性质”，这个条件其实很苛刻，大部分问题不满足。

动态规划则专门对付子问题重叠的情况。它承认子问题会被反复用到，所以老老实实把每个子问题的解存起来。同时它也不像贪心那样只顾眼前，而是通过状态转移方程，把所有的可能性都考虑进去，最终选出最优的那个。你可以这么理解：分治是各干各的然后拼起来，贪心是一条路走到黑，动态规划是做好笔记、步步为营。

2.3 最优子结构与重叠子问题

动态规划能用的前提是两个性质：最优子结构和重叠子问题。

最优子结构的意思是，大问题的最优解一定包含了子问题的最优解。拿最短路径来说，如果从A到C的最短路径经过B，那么A到B的那段一定也是最短的，B到C的那段也一定是最短的。如果不是，你换一条更短的，整体不就更短了吗？这就矛盾了。所以只要问题具有最优子结构，我们就可以放心地从子问题的最优解推导大问题的最优解。

重叠子问题的意思是，在递归求解的过程中，同一个子问题会被多次遇到。爬楼梯那个例子就是典型，f(3)在算f(5)和f(4)时都被用到了。如果子问题不重叠，那用分治就好了，没必要上DP。

这两个性质缺一不可。没有最优子结构，你从子问题推不出大问题；没有重叠子问题，你记录中间结果也没意义，白白浪费空间。

注意：很多人误以为“最优子结构”就是“局部最优能推出全局最优”，这其实是贪心的思路。最优子结构说的是大问题的最优解里面包含了子问题的最优解，但不代表你每一步都选局部最优就能得到全局最优。这个区别一定要想清楚。

3. 状态设计：动态规划最核心也最难的一步

3.1 状态到底是什么

如果把动态规划比作盖房子，那状态就是砖块，转移方程就是水泥。没有砖块，水泥再多也砌不成墙。状态设计对了，转移方程往往水到渠成；状态设计错了，怎么推都推不出来。

那状态到底是什么？简单说，状态就是你对当前局面的一个完整描述。它必须包含足够的信息，使得从这个状态出发，你能做出下一步的决策，并且能判断这个状态的好坏。同时，状态又不能包含多余的信息，否则状态空间会爆炸。

拿爬楼梯来说，状态就是“当前在第几级台阶”。这个信息足够了，因为从第i级台阶出发，你只需要知道i是多少，就能决定下一步走到i+1还是i+2。至于你之前是怎么走到第i级的，走了多少步，用了什么姿势，统统不重要。这就是状态的“无后效性”——当前状态一旦确定，后续的决策只依赖于当前状态，与到达这个状态的路径无关。

3.2 一维状态与多维状态的取舍

状态可以是多维的。爬楼梯是一维状态，因为只需要一个变量就能描述局面。但很多问题一个变量不够用。

比如经典的“零钱兑换”：给你若干种面额的硬币，问凑出金额n最少需要几枚硬币。这里状态是“当前需要凑出的金额”，还是一维的。但如果加一个限制条件，比如每种硬币最多只能用一次，那状态就变成二维了：dp[i][j]表示用前i种硬币凑出金额j的最少硬币数。因为你需要知道“现在考虑到第几种硬币了”和“还需要凑多少钱”这两个信息。

再比如“最长公共子序列”，两个字符串，状态自然是二维的：dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列长度。因为你需要同时知道两个字符串各自处理到哪了。

那什么时候该加维度？判断标准很简单：如果你发现当前状态不足以做出下一步决策，或者不足以判断当前局面的优劣，那就说明缺信息，需要加维度。但每加一维，状态空间就乘一个量级，时间和空间复杂度都会上去。所以要在“信息足够”和“空间可控”之间找平衡。

3.3 状态的无后效性为什么重要

无后效性是状态设计的一条铁律。它的意思是：一旦当前状态确定了，未来只与当前状态有关，与怎么到达当前状态的历史路径无关。

为什么这条这么重要？因为如果未来依赖于历史路径，那你的状态就必须把历史路径也编码进去，状态空间会变得无比巨大，动态规划就退化成暴力搜索了。

举个例子。假设你在玩一个游戏，角色有生命值和魔法值两个属性。如果你设计的状态是“当前生命值和魔法值”，那没问题，因为下一步能做什么只取决于当前的血量和蓝量。但如果你设计的状态是“当前生命值、魔法值、以及之前每一步的选择”，那就完蛋了，状态多到没法存。

所以设计状态的时候，一定要问自己：我记录的信息，是否足以唯一确定后续的决策？如果两个不同的历史路径到达了同一个状态，它们后续的最优决策是否相同？如果相同，说明状态设计是合理的；如果不同，说明状态里缺了关键信息，需要补上。

实操心得：我刚开始学DP的时候，经常犯一个错误——状态里塞了太多没用的信息。比如做背包问题，非要把“当前背包里装了哪些物品”也记下来。其实完全没必要，因为背包问题只关心“当前容量还剩多少”和“当前考虑到第几个物品了”，具体装了哪些物品不影响后续决策。状态越精简，效率越高。

4. 转移方程：从状态到状态的桥梁

4.1 转移方程的本质是决策枚举

状态设计好了，接下来就是转移方程。转移方程说白了就是：在当前状态下，你有哪些选择？每个选择会导致什么后果？哪个后果最好？

用数学语言说，转移方程就是dp[state] = opt{ dp[prev_state] + cost }，其中opt是最优化操作（取最大、最小、求和等），prev_state是做出某个决策后到达的前一个状态，cost是这个决策的代价。

还是拿爬楼梯举例。状态dp[i]表示走到第i级的走法数。在当前状态i下，你只能从i-1或i-2走过来。所以dp[i] = dp[i-1] + dp[i-2]。这里的“决策”就是“最后一步是走1级还是走2级”，两种决策对应的前一个状态分别是i-1和i-2，代价都是1种走法，所以加起来。

再拿零钱兑换举例。状态dp[j]表示凑出金额j所需的最少硬币数。在当前状态j下，你可以选择任何一种面额的硬币coin。如果选了coin，那你就从状态j-coin转移过来，代价是1枚硬币。所以dp[j] = min{ dp[j-coin] + 1 }，对所有满足coin <= j的硬币面额取最小值。

你看，转移方程的核心就是枚举所有可能的决策，然后从中选出最优的。枚举的范围取决于问题本身，但思路是通用的。

4.2 边界条件：别让程序在起点就翻车

转移方程描述了状态之间怎么跳，但总得有个起点。边界条件就是那些不需要转移、可以直接给出答案的状态。

爬楼梯的边界是dp[0] = 1（站在地面，不动就是一种走法）和dp[1] = 1（走到第1级只有一种走法）。零钱兑换的边界是dp[0] = 0（凑出金额0不需要任何硬币）。最长公共子序列的边界是dp[0][j] = 0和dp[i][0] = 0（任意字符串和空串的公共子序列长度都是0）。

边界条件看起来简单，但实际写代码的时候特别容易出错。我见过太多人转移方程推得漂漂亮亮，结果边界写错了，整个答案全盘皆输。比如爬楼梯，如果dp[0]设成0，那dp[2] = dp[1] + dp[0] = 1 + 0 = 1，但实际应该是2（走两次1级，或者一次走2级）。一个边界错误，后面全错。

注意：边界条件一定要根据问题的实际语义来确定，不能凭感觉。建议在草稿纸上手动算几个小规模的情况，验证边界值是否正确。比如爬楼梯，手动算一下n=0,1,2,3的情况，看看边界设成多少才能让结果对得上。

4.3 从递归到递推：两种实现路径

有了状态和转移方程，实现方式有两种：递归加记忆化，和递推填表。

递归加记忆化的写法更贴近转移方程的数学形式，代码通常更简洁，也更容易理解。思路是：写一个递归函数solve(state)，先查表看这个状态有没有算过，算过就直接返回；没算过就按照转移方程递归计算，算完存表再返回。这种写法也叫“自顶向下”。

递推填表的写法是：先确定状态的遍历顺序，然后从边界条件开始，一层一层往外推，直到算出目标状态。这种写法也叫“自底向上”。它的好处是没有递归栈开销，速度通常更快，而且方便做空间优化。

两种写法各有优劣。递归加记忆化写起来快，不容易搞错遍历顺序，但递归深度太大会爆栈。递推填表效率高，但需要想清楚遍历顺序，顺序错了结果就错了。

我的建议是：初学的时候先用递归加记忆化，因为它的结构和转移方程几乎一一对应，不容易出错。等熟练了，再改成递推填表，追求更高的效率。下面用爬楼梯举例，两种写法都给你。

递归加记忆化：

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

递推填表：

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

你看，递推版本里那个for循环的顺序就是从前往后，因为dp[i]依赖于dp[i-1]和dp[i-2]，所以必须先把小的算出来。如果依赖关系反过来，遍历顺序就要反过来。这就是为什么递推填表需要想清楚遍历顺序。

5. 实战拆解：从题目到代码的完整流程

5.1 案例一：最大子数组和

题目：给一个整数数组，找出一个连续子数组，使得它的和最大，返回这个最大和。

第一步，设计状态。最直接的想法是dp[i]表示“以第i个元素结尾的最大子数组和”。为什么强调“以第i个元素结尾”？因为子数组必须是连续的，如果dp[i]表示“前i个元素中的最大子数组和”，那转移的时候你没法判断第i个元素要不要接在前面的子数组后面。而“以第i个元素结尾”这个定义，天然保证了连续性。

第二步，推转移方程。对于dp[i]，第i个元素有两种选择：要么接在前面的子数组后面，要么自己单独成为一个子数组。如果接在后面，那和就是dp[i-1] + nums[i]；如果单独，和就是nums[i]。我们要最大的，所以dp[i] = max(dp[i-1] + nums[i], nums[i])。

第三步，确定边界。dp[0] = nums[0]，因为第一个元素结尾的子数组只有它自己。

第四步，确定答案。答案不是dp[n-1]，而是max(dp[0], dp[1], ..., dp[n-1])，因为最大子数组不一定以最后一个元素结尾。

代码实现：

def max_subarray(nums): n = len(nums) dp = [0] * n dp[0] = nums[0] ans = dp[0] for i in range(1, n): dp[i] = max(dp[i-1] + nums[i], nums[i]) ans = max(ans, dp[i]) return ans

这个题还可以做空间优化，因为dp[i]只依赖于dp[i-1]，所以用一个变量滚动更新就行，不需要整个数组。优化后空间复杂度从O(n)降到O(1)。

def max_subarray_optimized(nums): cur = nums[0] ans = nums[0] for i in range(1, len(nums)): cur = max(cur + nums[i], nums[i]) ans = max(ans, cur) return ans

实操心得：空间优化是动态规划进阶的必修课。很多DP问题的状态转移只依赖于前一层或前几个状态，这时候就可以用滚动数组或者变量来压缩空间。但要注意，空间优化之后代码的可读性会下降，如果是在面试中，建议先写未优化的版本，确认逻辑正确后再提优化思路。

5.2 案例二：最长递增子序列

题目：给一个整数数组，找出最长递增子序列的长度。子序列不要求连续，但要求保持相对顺序。

第一步，设计状态。dp[i]表示“以第i个元素结尾的最长递增子序列长度”。同样强调“以第i个元素结尾”，理由和上面一样。

第二步，推转移方程。对于dp[i]，我们需要往前看所有j < i且nums[j] < nums[i]的位置。如果nums[i]能接在nums[j]后面，那长度就是dp[j] + 1。我们要最长的，所以dp[i] = max(dp[j] + 1)，对所有满足j < i且nums[j] < nums[i]的j。

第三步，边界。每个元素至少可以自己构成一个长度为1的递增子序列，所以dp[i]初始值都是1。

第四步，答案。max(dp[0], ..., dp[n-1])。

代码实现：

def length_of_lis(nums): n = len(nums) dp = [1] * n ans = 1 for i in range(1, n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) ans = max(ans, dp[i]) return ans

这个题的时间复杂度是O(n^2)，因为有两层循环。它还有一个O(n log n)的优化解法，用到了贪心加二分查找，但那个解法已经不太像典型的动态规划了，这里先不展开。

5.3 案例三：零钱兑换

题目：给若干种硬币面额和一个目标金额，问凑出目标金额最少需要几枚硬币。每种硬币可以用无限次。

第一步，状态。dp[j]表示凑出金额j所需的最少硬币数。

第二步，转移方程。对于金额j，我们可以选择任何一种面额为coin的硬币。如果选了它，就相当于从金额j-coin转移过来，代价是1枚硬币。所以dp[j] = min(dp[j-coin] + 1)，对所有满足coin <= j的硬币面额取最小。

第三步，边界。dp[0] = 0，凑出金额0不需要硬币。其他dp[j]初始化为一个很大的数（比如无穷大），表示暂时无法凑出。

第四步，答案。dp[target]，如果它还是无穷大，说明无法凑出，返回-1。

代码实现：

def coin_change(coins, amount): INF = float('inf') dp = [INF] * (amount + 1) dp[0] = 0 for j in range(1, amount + 1): for coin in coins: if coin <= j: dp[j] = min(dp[j], dp[j - coin] + 1) return dp[amount] if dp[amount] != INF else -1

注意这里的遍历顺序：外层循环遍历金额，内层循环遍历硬币。为什么不能反过来？因为每种硬币可以用无限次，如果外层遍历硬币、内层遍历金额，那对于每种硬币，你只能沿着金额递增的方向更新一次，无法实现“同一种硬币用多次”的效果。外层遍历金额、内层遍历硬币，才能保证每种硬币在任意金额下都可以被重复选择。

注意：背包类问题的遍历顺序非常讲究。0-1背包要求每种物品只能用一次，所以外层遍历物品、内层遍历容量且容量从大到小；完全背包要求每种物品可以用无限次，所以外层遍历物品、内层遍历容量且容量从小到大。如果搞反了，0-1背包会变成完全背包，完全背包会变成0-1背包。这个坑我踩过不止一次，每次都要在草稿纸上画一遍才放心。

6. 常见问题与排查技巧实录

6.1 状态转移方程推不出来怎么办

这是最常见的问题。很多人卡在这一步，盯着题目发呆，不知道怎么从子问题推到父问题。

我的经验是：不要硬推，先手动模拟。拿一个具体的小例子，在纸上一步一步算，看看每一步的答案是怎么从前面几步的答案算出来的。比如爬楼梯，你手动算n=1,2,3,4,5，把结果列出来，然后观察规律。很多时候，规律一出来，转移方程就跟着出来了。

另一个技巧是“从最后一步倒推”。问自己：到达最终状态的前一步可能是什么？把所有可能的前一步列出来，然后看当前状态和前一步状态之间的关系。这个方法对很多问题都有效，因为最终状态往往是问题最明确的地方。

如果还是推不出来，那可能是状态设计有问题。回头检查一下：状态是否包含了足够的信息？是否满足无后效性？如果状态本身就不对，转移方程当然推不出来。

6.2 边界条件总是写错怎么办

边界条件写错，通常是因为没有想清楚“最小规模的问题是什么”。我的建议是：在写代码之前，先把n=0,1,2,3的情况手动算一遍，把结果写在纸上。然后写代码的时候，用这些手动算的结果去验证边界条件。

另外，边界条件不一定是dp[0]或dp[0][0]。有些问题的边界是多个，比如最长公共子序列，dp[0][j]和dp[i][0]都是边界。有些问题的边界需要特殊处理，比如零钱兑换中dp[0]=0但其他dp[j]初始化为无穷大。所以一定要根据具体问题来确定边界，不能套模板。

6.3 遍历顺序搞反了怎么发现

遍历顺序搞反的典型症状是：代码逻辑看起来没问题，但结果就是不对，或者部分测试用例通过、部分不通过。

发现的方法很简单：在代码里加打印，把每一步的状态值输出出来，和手动模拟的结果对比。如果发现某个状态的值依赖于一个还没被计算的状态，那就说明遍历顺序反了。

比如0-1背包问题，如果内层容量从小到大遍历，那dp[j]会依赖于dp[j-weight]（已经在本轮被更新过），相当于同一个物品被用了多次。这时候你打印dp数组，会发现结果比正确答案大，因为物品被重复使用了。把容量改成从大到小遍历，问题就解决了。

6.4 空间优化后结果不对怎么排查

空间优化之后结果不对，通常是因为优化后的变量没有正确初始化，或者更新顺序有问题。

排查方法：先写一个未优化的版本，确认结果正确。然后逐步优化，每优化一步就对比一次结果。如果优化后结果变了，说明优化过程中引入了bug。常见的bug包括：滚动数组的初始值没设对、变量更新顺序反了导致使用了新值而不是旧值、多维数组压缩成一维时索引搞错了。

实操心得：空间优化虽然能降低空间复杂度，但会牺牲代码的可读性和可调试性。我的建议是：除非空间确实不够用，或者面试官明确要求优化，否则优先保证代码的正确性和可读性。毕竟，一个能跑对的O(n)空间解法，比一个跑不对的O(1)空间解法有价值得多。

6.5 常见问题速查表

7. 我个人在DP学习路上的一些体会

动态规划这东西，入门难，精通更难。但它的难不是那种“看不懂”的难，而是“想不到”的难。代码本身往往很短，十几行就写完了，但背后的思考过程可能要好几个小时。

我自己的经验是，学DP一定要动手。看别人的题解，觉得“哦，原来是这样”，和自己独立推出来，完全是两码事。我建议每学一个新的DP类型，至少独立做五到十道同类题，做到不看题解也能推出状态和转移方程为止。这个过程很痛苦，但熬过去之后，你会发现自己的思维方式真的变了。

另外，不要追求刷题数量。DP的题型是有限的，经典的就那么几十种。与其刷两百道题但每道都似懂非懂，不如把二十道经典题吃透，每道都能讲清楚状态为什么这么设计、转移方程为什么这么写、边界为什么这么定。质量比数量重要得多。

最后说一个我踩过的坑：不要一上来就追求最优解。很多人看到O(n)的解法就觉得自己O(n^2)的解法拿不出手，其实完全没必要。先把O(n^2)的解法写对，再考虑优化。一个正确的暴力DP，比一个错误的优化DP有价值一百倍。优化是锦上添花的事，正确性才是底线。

这篇是动态规划拆解的第一篇，主要把状态设计、转移方程、边界条件、遍历顺序这些基础但核心的东西讲透了。下一篇我打算聊背包问题的几种变体，以及区间DP和树形DP的入门思路。如果你跟着这篇的内容把爬楼梯、最大子数组和、最长递增子序列、零钱兑换这几个例子都亲手实现一遍，那DP的基础就算是打牢了。剩下的，就是多练、多想、多总结。