企业官网建设流程全解析

做算法题这些年，跟圈子里的朋友交流，大家公认最难啃的名字就是动态规划法。十个新手里有八个第一次看到它，都会觉得这是块硬骨头：状态、转移方程、最优子结构、重叠子问题，术语一个接一个，教材上的公式一大片，真到自己动手做题的时候却不知道从哪下笔。这篇文章不是想罗列更多抽象概念，而是给你一套能直接用的思考方法和做题流程。只要你能把一道递归题写出来，顺着这套流程，就能把它变成一道动态规划题。适合刚接触算法、准备面试笔试，以及被各种“神级状态设计”劝退的读者。

1. 动态规划到底在干什么：先治好“重复计算”这个病

1.1 从最普通的递归开始：为什么斐波那契会越算越慢

先说一个最简单也最经典的问题：求第 n 个斐波那契数。公式大家都知道，f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)。绝大多数人第一次接触递推就是从这开始的，也很容易写出下面这种递归代码：

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

代码漂亮，逻辑没问题，但你把 n=40 传进去试试，几秒钟都不一定算得出来；n=45 就更夸张，笔记本风扇直接起飞。原因很多人也听说过：重复计算。但你有没有真正数过到底重复了多少？

我带你画一下调用过程。求 f(5)，需要 f(4) 和 f(3)；求 f(4) 需要 f(3) 和 f(2)。注意，这里的两个 f(3) 本身就是完全相同的子问题，但递归程序根本不记得上一个 f(3) 算出来过，白白再算一遍。继续往下展开，f(2) 更是被反复调用好多次。

这个计算的浪费程度是指数级的。用递推式可以算出，朴素递归求解 f(n) 的时间复杂度是 O(2^n)。n 从 40 涨到 42，只是多了两层递归，运行时间却翻了好几倍。这就是很多入门者第一次被算法复杂度打脸的时刻。

问题不在“递归”本身，而在“不记性”。同样的子问题，算一次和算一万次，结果不会有任何变化，程序却傻乎乎地每次都重头推演。

1.2 一张表改变一切：从小问题往大问题递推

理解了痛处之后，解决办法其实很朴素：既然 f(3) 会被反复调用，那我第一次算出 f(3) 时就把它存到一个数组里，后面谁要用就直接查表，不用再递归展开。

顺着这个思路，先看最自然的两种写法。第一种叫记忆化搜索，也叫自顶向下。代码还是递归的样子，只是加一个缓存：

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

第二种叫自底向上递推，也是我更推荐初学者掌握的写法。它的顺序恰好反过来，从 f(0)、f(1) 开始，一步一步往上推，把结果存在数组里：

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

看到这里你应该已经感觉到了，动态规划并没有多玄乎。它做的核心事情就是：把大规模问题的结果拆成小规模问题的结果，从小到大把所有的“中间结果”都算一遍并保存，最后用这些中间结果合成最终答案。在斐波那契这个例子里，dp 数组就是那张“记答案的表”，填表的过程就是从小到大的递推过程。

时间复杂度从指数级降到了 O(n)，根本原因就是每个子问题只算一次。这件事值得单独拎出来说：动态规划本质上是在用空间换时间。你多开了一个数组，换来的是计算量从指数级崩塌成多项式级。后面你会看到，几乎所有 DP 优化，翻来覆去都是在这个“空间换时间”的基础上做文章。

2. 什么样的题目才配用动态规划：两个硬性条件

很多同学学 DP 最大的困惑，不是不会写递推，而是不知道“这道题到底该不该用 DP”。有些题一眼像贪心，有些题一看像二分，还有些题根本看不出规律。我一般给新人的建议是先别急着套模板，先拿两个标准去筛一下这题配不配用动态规划。

2.1 最优子结构：大问题的最优解能不能拆成子问题的最优解

第一个条件是最优子结构。听起来绕口，翻译成人话就是：一个大问题的最优答案，能不能由它内部几个小问题的最优答案直接组合出来。

拿最经典的带权最短路径举例。假设你想找从 A 点经过一系列城市到 E 点的最短路线，而且这条最短路线确实经过了中间城市 C。那么从 A 到 C 的这一段路线，一定也是 A 到 C 的所有路线里最短的。为什么？因为如果存在一条更短的 A 到 C 路线，我用它替换掉原来那段，整条 A 到 E 的路程还能继续变短，这跟“当前已经是全局最短路”矛盾。

这种“大问题最优解里天然含着子问题最优解”的性质，就是最优子结构。它给了我们一个拆分问题的底气：我可以放心大胆地把原问题切成若干个子问题，先各自求最优，再拼出原问题的最优。

反过来，有些问题就不满足这个性质。比如在无向图里找一条从 A 到 E 的最长简单路径，路径中间经过了 C。这段 A 到 C 的路径，在很多情况下并不是 A 到 C 的最长路径，因为要保证整条路不能重复经过节点。你强行让子问题取“最优”，反而可能破坏全局的约束条件。这类问题用 DP 或者贪心就是错的，只能退回去用搜索或状压。新手分不清 DP 和贪心的时候，先拿这个性质过滤一遍，能避免很多无效尝试。

2.2 重叠子问题：递归树里重复的节点有多少

第二个条件是重叠子问题。意思很好理解：如果把问题拆成子问题后，各个子问题之间大量存在“同一个问题被算了好几次”的情况，就说明它具备重叠子问题。

斐波那契数列就是最典型的例子，f(5) 依赖 f(4) 和 f(3)，而 f(4) 又依赖 f(3)，子问题 f(3) 被反复需要。反过来看归并排序，一个数组拆成左右两半，左半排序和右半排序是互不相干的独立子问题，彼此之间没有任何重复，那就谈不上重叠子问题，用普通分治就够了。

所以判断用不用动态规划，可以简单问自己两个问题：第一，大问题的最优解能不能用子问题最优解拼出来？第二，拆出来的子问题是不是大量重复？都满足，基本就可以确定走 DP 路线了。只满足第一个但不满足第二个，通常用分治或贪心；两个都不满足，老老实实去搜索。

我在实际刷题的时候，还会额外加一个感受型判断方式：一道题如果给你一个“规模 n”的参数，暴力枚举时是指数级复杂度，而且你隐隐觉得这个答案可以从小到大递推着算，那八成就是 DP。这种只可意会的判断，刷满三十道经典题之后自然就有了。

3. 拿到DP题先别急着写码：完整四步法

很多新手一看到 DP 题就慌，赶紧回忆背过的模板，结果题目稍微变个套路就傻眼。我的建议是，不管什么 DP 题，你先把下面四件事想清楚再动手：状态定义、转移方程、初始化、答案位置。这四个东西串起来，就是完整解法。

3.1 定义状态：把“dp[i]表示什么”说清楚

第一步是定义状态。这一点最抽象，也最容易被忽视。状态说白了就是你要填的那张表的行和列分别代表什么。比如斐波那契数列里 dp[i] 表示“第 i 个斐波那契数”，爬楼梯问题里 dp[i] 表示“爬到第 i 级台阶的方案总数”。

定义状态有一条偷懒的技巧：直接从问题本身的问法出发。题目问“最大值是多少”，状态里就带上“长度为 i 时的最大值”；题目问“有多少种方案”，状态里就带“到第 i 个位置的方案数”；题目给了两个字符串或者两堆物品，通常就在状态里放两个维度，比如 dp[i][j] 表示“处理到第一个串的前 i 个字符、第二个串的前 j 个字符时的答案”。

状态定义一定要做到“无歧义、不遗漏、可转移”。尤其是很多字符串类题目，我强烈建议统一写成“前 i 个字符”而不是“第 i 个字符”，这样后面写转移和初始化都会省很多麻烦，不容易出现索引越界的怪异错误。

3.2 转移方程、初始化与答案定位

第二步是写转移方程，也就是回答“dp[i] 是怎么从前面的状态推导出来的”。怎么想转移？我有一套很实用的方法，叫“看最后一步”。你不要从第一项开始想，而是倒过来想：假设现在已经到了第 i 步，到达这个状态的最后一步有哪些可能？

以爬楼梯为例：一共 n 级台阶，每次可以爬 1 级或 2 级，问有多少种不同的方法爬到顶。最后一步从哪来？要么是从第 i-1 级跨 1 级上来，要么是从第 i-2 级跨 2 级上来。因此，爬到第 i 级的总方案数，就是“爬到第 i-1 级的方案数”加上“爬到第 i-2 级的方案数”。转移方程自然是 dp[i] = dp[i-1] + dp[i-2]。

第三步是初始化。初始化不是随便设几个 0 就完了，它是递推的地基，地基错了整栋楼都歪。爬楼梯问题里 dp[1] = 1，dp[2] = 2，这两个边界必须单独给。很多 DP 题从 dp[0] 甚至空状态开始定义，比如后面会讲的编辑距离，dp[0][j] 和 dp[i][0] 都要仔细处理。

第四步是确定答案在哪。有的答案是 dp[n]，有的是 dp 数组里的最大值，还有的是 dp[m][n] 这种二维表的右下角。这一步看起来简单，但在区间型 DP 或者背包问题里，答案位置很容易找错。我的习惯是写完代码前，先在纸上把整个 dp 表格画出来，用笔头模拟填充一遍，答案在哪个格子是一目了然的。

4. 三种高频DP模型，照着套就行

算法题里的 DP 虽然多，但高频套路就那么几类。我挑三个最有代表性的模型出来，线性 DP、背包 DP、字符串二维 DP。把这三类的推导过程吃透，你已经能解决很大一部分 DP 题目了。

4.1 线性DP：最长递增子序列的推导全过程

第一个模型是线性 DP，代表题目是“最长递增子序列”，也就是 LIS。问题描述也很简单：给一个数组，找出其中最长的严格递增子序列长度。注意“子序列”不要求连续，这是它和“连续子数组”最大的区别。

我第一次做这题时，第一反应是暴力枚举所有子序列，复杂度 2^n，根本不可能。后来才知道用 DP 可以在 O(n^2) 内解决。状态怎么定义？这里有一个关键点：如果只定义 dp[i] 为“前 i 个数的最长递增子序列长度”，转移会非常难写，因为你不知道以谁结尾，无法判断能否接上去。

正确的状态是：dp[i] 表示“以第 i 个元素结尾的最长递增子序列的长度”。这样转移就清晰了：对于每个 j < i，只要 nums[j] < nums[i]，nums[i] 就能接到以 nums[j] 结尾的递增子序列后面，长度为 dp[j] + 1。遍历所有满足条件的 j，取最大值。

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

注意 dp 数组初始化全部为 1，因为每个元素都可以单独成为一个长度为 1 的子序列。答案不是 dp[n-1]，而是整个 dp 数组里的最大值。这个“答案在数组里取 max”的模式，在线性 DP 里非常常见，新手容易漏。

如果你还想继续优化，LIS 有 O(n log n) 的做法，核心是维护一个 tails 数组，tails[k] 表示长度为 k+1 的递增子序列的最小尾部元素，然后用二分查找更新。代码如下：

import bisect def length_of_lis_optimized(nums): tails = [] for x in nums: pos = bisect.bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails)

这个优化的思路就不展开细讲了，面试时能写出 O(n^2) 并讲清楚 DP 思路已经算过关，O(n log n) 属于加分项。

4.2 0/1背包：从二维递推到一维优化

第二个模型是背包 DP，这里只讲最核心的 0/1 背包。问题描述：有 n 个物品，每个物品有重量 weights[i] 和价值 values[i]，背包容量为 capacity，每个物品最多选一次，问能装的物品最大总价值是多少。

状态定义是二维的，dp[i][j] 表示“考虑前 i 个物品，背包容量为 j 时能获得的最大价值”。为什么要两维？因为既要记录处理到哪个物品，又要记录剩余容量。

转移时，对于第 i 个物品，只有两种决策：不选它，那么状态从 dp[i-1][j] 原样继承，价值不变；选它，前提是 j >= weights[i]，那么状态从 dp[i-1][j - weights[i]] 转移过来，再加上 values[i]。所以转移方程是：

def zero_one_knapsack(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity]

我这里直接给的是空间压缩后的写法，dp 从二维变成一维。原理是：计算第 i 个物品时，只需要上一轮的结果。但压缩后遍历容量 j 必须从大到小，也就是倒着遍历。为什么？因为如果正序遍历，dp[j - weights[i]] 可能已经被当前这个物品更新过了，等于把同一个物品重复选了多次，这就不是 0/1 背包而是完全背包了。倒序遍历能确保 dp[j - weights[i]] 还是上一轮（也就是还没装当前物品）的值。

这个倒序遍历是背包问题最经典的坑，没有之一。面试时我经常先故意写成正序，再问对方“为什么结果不对”，绝大多数人表达不清楚。你只要把这一点彻底吃透，0/1 背包基本就掌握了。

4.3 二维字符串DP：编辑距离

第三个模型是字符串类二维 DP，代表题是编辑距离。题目要求：给你两个单词 word1 和 word2，每次操作可以插入一个字符、删除一个字符或者替换一个字符，计算把 word1 变成 word2 所需的最少操作次数。

状态定义很自然：dp[i][j] 表示把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。注意这里是“前 i 个”，也就是从 1 计数，比 0 计数好处理。代码实现如下：

def min_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min( dp[i - 1][j] + 1, # 删除 word1 的一个字符 dp[i][j - 1] + 1, # 插入一个字符到 word1 dp[i - 1][j - 1] + 1 # 替换一个字符 ) return dp[m][n]

先看初始化：dp[i][0] 表示把 word1 的前 i 个字符变成空串，只能全删，所以是 i；dp[0][j] 表示把空串变成 word2 的前 j 个字符，只能全插，所以是 j。这两行是二维表的地基。

再看转移：如果两个字符相等，那这一位不需要额外操作，直接继承前一位的状态 dp[i-1][j-1]；如果不相等，则考虑三种操作的最小值。这个题活生生展示了二维 DP 的填表逻辑：每个格子只依赖左、上、左上三个方向，你在纸上手动填一遍 3x3 的表，所有转移一下就通了。

刷 DP 题时，像编辑距离这种二维问题，我建议一定要在纸上画几次表格。很多人代码写了半天不知道怎么错，其实只要手算一个小数据就立刻明白了。

5. 优化与实现细节：这些坑我替你踩过了

基础写法会了之后，接下来是实战中绕不开的优化与细节问题。很多时候你的思路是对的，但代码就是跑不过，问题基本都出在这一节讲到的几件事上。

5.1 自顶向下记忆化与自底向上填表怎么选

理解了 DP 的原理之后，新手往往会陷入一个纠结：记忆化搜索和递推填表到底用哪个？我个人的习惯是分阶段。

如果你是在学习阶段，对题目思路还不清晰，我强烈建议先写记忆化搜索。因为它跟你熟悉的递归结构基本一致，只需要加一个缓存数组，思维负担最小。一旦递归的终止条件和调用关系写对了，状态转移也就跟着对了，不容易出现递推循环顺序写错的低级错误。

如果是正式比赛、面试手写或者追求性能的场景，我更推荐自底向上的递推。因为递推没有递归调用栈的额外开销，也不用担心递归深度太大导致栈溢出。Python 的默认递归深度大概在 1000 层左右，但有些 DP 题的状态依赖链可能超过几万层，递归就炸了。

其实两者在很多情况下可以互相转换。我的标准流程是：先用记忆化搜索快速理清状态转移，确认正确后，再翻译成自底向上的递推版本，最后按需做空间优化。

5.2 滚动数组：空间压缩时必须搞懂的遍历方向

空间优化是 DP 从“能跑”迈向“跑得好”的关键一步。很多二维 DP 其实每一刻只需要上一行的数据，比如编辑距离，dp[i][j] 只用到 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]，所以理论上只需要两行数组滚动使用，可以把空间从 O(m*n) 降到 O(n)。

滚动数组最简单的做法是用两个一维数组交替保存，old 和 new，每一轮计算完再互换。但更常见也更考验人的，是像 0/1 背包那样的单数组覆盖。单数组覆盖时，遍历方向必须分清楚：

• 0/1 背包：容量 j 需要倒序遍历，防止同一个物品被重复选择。
• 完全背包（每个物品可以选无限次）：容量 j 需要正序遍历，因为要允许重复选择当前物品。

很多同学把这两个搞混，背答案是记不住的。我提供一个理解角度：单数组覆盖时，倒序表示“这一轮更新时，被依赖的数据还是上一轮的”；正序表示“被依赖的数据随时可能被本轮结果覆盖”。你想让当前物品能不能被选多次，就决定让容量往哪个方向走。只要把这个想通，以后再遇到“正序还是倒序”的题，都不会再错。

5.3 状态设计与索引细节：初值、-inf、开n+1

最后一个特别磨人的点是细节。我在指导别人改代码时，发现大部分超出样例的错误，都出在三类细节上。

第一，dp 数组开的大小。状态里有 i 和 j 两个维度时，数组要开成 (n+1) 的大小。因为你用的往往是“前 i 个”这种从 1 开始计数的语义，0 留给空集或空串。漏开一位是索引越界的头号原因。

第二，初始值的含义要分清楚。DP 求最大值时，有些状态根本不可达，不能初始化为 0，而是要初始化为一个很小的负数，比如 float("-inf")。举个例子，背包问题里如果物品重量有大有小，dp[j] 的某些 j 值可能根本无法由任何物品的组合达到，初值为 0 在很多情况下也没问题；但在另一些“恰好装满”的变种题里，初值为 0 就会让非法状态也参与转移，结果全是错的。

第三，注意数值范围。方案数类 DP 很容易突破 int 范围，Python 本身没有这个问题，但如果用 C++ 就要记得上 long long。我见过太多人题目没特意提醒，结果用 int 一测，大样例直接溢出成负数，检查半小时不知道错在哪。这四件事可以在写代码之前先确认一遍，能省掉大量调试时间。

6. 常见Bug排查与调试点

做 DP 题最气人的是，代码看着啥都对，一跑就错。我把这几年遇到的常见 Bug 整理成了下面几张“病历”，每一条都配了对应的排查方法，希望对你有用。

6.1 转移方程写反是最隐蔽的错误

临床表现为：小数据能过，大数据莫名其妙错。多半是状态转移依赖的方向搞反了。比如最长递增子序列，正确写法是拿 j < i 的状态去更新 dp[i]，有人一着急写成从 i 往后面更新，最后 max 出来的结果偏大或偏小，还很难肉眼发现。

排查方法很笨但很有效：挑一个长度 5 以内的测试用例，把 dp 数组在每轮循环后的值打印出来，亲手画一遍推导过程。只要代码和手推结果对不上，错误位置立刻暴露。写 DP 题时脑子里要始终清楚“当前状态依赖哪些更小的状态”，一旦依赖关系不明确，就先把手推过程写出来再动键盘。

6.2 初始化漏掉边界，答案永远不对

初始化错误是另一种高频 Bug。典型表现是：空串、空数组、容量为 0、台阶只有 1 级这类“边界小状态”没处理，导致所有转移都建立在错误的地基上。

以编辑距离为例，dp[0][j] 表示从空串变到目标串，只能靠不断插入字符，所以必须初始化成 j。如果你漏了这行，后面所有 dp[1][1] 的计算都会用到错误数据，最后答案差得离谱。我建议拿到一道新 DP 题，先在草稿纸上写出 0、1、2 这三个最小规模的手算答案，再回头检查初始化能不能推出这些值，能对上再开始写全套代码。

6.3 调试三板斧：打表、暴力对拍、手推小样例

说到底层调试技巧，我习惯用三板斧。

第一板斧是打表。把中间 dp 数组每一轮打印出来，观察数值是不是逐层合理递推。状态数不多时直接肉眼找规律；状态多就挑几行打印，不全部输出。

第二板斧是暴力对拍。自己写一个完全不用 DP 的暴力解，比如枚举所有可能方案，和 DP 结果对比。随机生成小规模数据，跑几百组，一旦输出不一致，就把那一组数据缩小后再找到最小复现用例。这是我现在做算法题最依赖的方法，没有之一。

第三板斧是手推小样例。我特别推荐用纸笔推一个 3x3 或者 5 个元素的小表，从初始化开始一格一格填。很多时候填完一遍，代码里哪里写反了、哪里多加了 1，自己在填表过程中就意识到了。别嫌麻烦，这一招对二维 DP 尤其有用。

我常跟身边朋友说，DP 题卡住的时候，困在人脑里复盘代码是最低效的。去洗手间冷静一下，回来画一张小表，或者对拍一个暴力解，往往几分钟就能定位问题。

最后说一点个人经验。动态规划法最劝退人的地方，其实是心理门槛。很多人老想着“我要一眼想到巧妙的转移方程”，其实没必要。初学者做 DP，就应该多写暴力递归，把子问题的调用关系看清，然后一步一缓存，再翻译成递推。我见过很多“DP 学不明白”的人，最后都是靠这个方法慢慢开窍的。刷题不需要急，把状态定义说清楚、把转移方程推导明白，顺手能把边界值验一遍，代码只是最后一步的翻译工作。