企业官网建设流程全解析

1. 从递归的痛点到动态规划的甜点

如果你刷过算法题，大概率经历过这样的场景：写了一个自认为优雅的递归解法，结果提交后系统提示超时，一看数据规模才三十几，但你的程序跑了十几秒还没出结果。更诡异的是，把递归改成带记忆化的版本，代码几乎没怎么变，运行时间直接从十几秒掉到几毫秒。这个从“慢得离谱”到“快得飞起”的转折点，就是动态规划要解决的核心问题。

动态规划（Dynamic Programming，简称DP）这个名词听起来很唬人，但它的本质可以用一句话概括：把一个大问题拆成若干重叠的子问题，把子问题的解存起来，避免重复计算，最终拼出大问题的解。注意这里有两个关键词——“重叠”和“存起来”。如果子问题之间没有重叠，那叫分治，不叫DP；如果算完了不存，那就是普通递归，该慢还是慢。

我刚开始学DP的时候，最大的困惑不是“这题怎么做”，而是“我怎么知道这题该用DP”。后来刷了上百道题才慢慢摸出门道：凡是问题可以拆成“前一步的选择影响后一步的状态”，并且你发现暴力递归里同一个参数组合被反复计算，那基本就是DP的菜。比如经典的爬楼梯问题，你爬到第n阶的方法数，等于爬到第n-1阶的方法数加上爬到第n-2阶的方法数，因为最后一步要么跨一阶要么跨两阶。这个递推关系一出来，DP的骨架就有了。

这篇文章我会从实战角度出发，把动态规划的学习路径拆成几个关键阶段：先理解为什么暴力递归会爆炸，再掌握记忆化搜索这个“救命稻草”，然后自然过渡到递推形式的DP，接着聊状态设计和转移方程这两个最容易翻车的地方，最后用几个经典模型把套路串起来。不管你是刚接触DP的新手，还是刷题时总在DP题上卡壳的老手，应该都能从中找到对自己有用的东西。

2. 暴力递归为什么会指数级爆炸

2.1 用斐波那契数列看清重复计算的规模

斐波那契数列几乎是所有讲DP的文章都会用的例子，但很多人只是把它当个引子，没有真正算过重复计算到底有多夸张。我们来看最朴素的递归写法：

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

这段代码的逻辑没问题，但执行过程是一棵巨大的递归树。计算fib(5)需要fib(4)和fib(3)，计算fib(4)又需要fib(3)和fib(2)，你会发现fib(3)被计算了两次，fib(2)被计算了三次。随着n增大，重复计算的次数呈指数增长。具体来说，计算fib(n)的时间复杂度是O(2^n)，因为递归树近似一棵满二叉树。

我实际测试过，当n=40时，这段代码在我的机器上跑了大约30秒；n=45时，直接超过5分钟。而n=40在算法题里根本不算大，很多题目的数据规模动辄10^5，用这种递归必死无疑。

问题的根源在于：同一个子问题被反复求解，每次求解都从头算一遍。这就像你每次做菜都要重新去菜市场买一遍所有调料，哪怕冰箱里已经堆满了上次买多的。解决思路很直接——把算过的结果记下来，下次要用直接取。

2.2 记忆化搜索：给递归加一个备忘录

记忆化搜索（Memoization）的思路简单到令人发指：用一个数组或哈希表记录每个子问题的答案，递归之前先查表，如果算过了就直接返回。

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

改动只有三行：初始化备忘录、查表、存表。但效果是颠覆性的——时间复杂度从O(2^n)直接降到O(n)，因为每个子问题最多被计算一次。n=1000也能瞬间出结果。

这里有个细节值得注意：备忘录的key必须能唯一标识一个子问题。在斐波那契里，子问题只由n决定，所以key就是n。但在更复杂的问题里，子问题可能由多个参数共同决定，比如“从第i个物品开始选，剩余容量为j时的最大价值”，那key就是(i, j)这个组合。如果key设计错了，要么查不到已算的结果，要么把不同子问题当成同一个，答案就错了。

提示：记忆化搜索的代码结构和暴力递归几乎一样，只是多了查表和存表两步。如果你能写出暴力递归，改成记忆化搜索就是几分钟的事。这是学习DP最平滑的切入点。

2.3 从记忆化到递推：两种写法的取舍

记忆化搜索虽然好用，但它有两个小问题：一是递归调用有栈开销，数据规模特别大时可能爆栈；二是递归的依赖方向是“从大往小”，而很多问题的自然推导方向是“从小往大”。于是就有了递推形式的DP——先算小规模子问题，再用它们拼出大规模子问题的答案。

斐波那契的递推写法：

def fib(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[1]开始，依次算出dp[2]、dp[3]……直到dp[n]。每个状态只依赖前两个状态，所以还可以进一步把空间优化到O(1)，只用两个变量滚动更新。

那到底该用记忆化搜索还是递推？我的经验是：如果状态转移的方向很清晰、依赖关系是线性的，优先写递推；如果状态之间的依赖比较复杂、不好确定计算顺序，先用记忆化搜索把答案跑通，再考虑改写成递推。面试时如果时间紧张，记忆化搜索往往更快写对，因为它直接对应暴力递归的结构。

3. 状态设计与转移方程：DP的两根支柱

3.1 状态定义决定了问题能不能解

DP最难的地方从来不是写代码，而是定义状态。状态定义对了，转移方程往往水到渠成；状态定义错了，怎么推都推不出来。

什么叫状态？简单说，状态就是“子问题的参数化描述”。比如爬楼梯问题，状态可以定义为“爬到第i阶的方法数”，用dp[i]表示。这个定义之所以有效，是因为它满足两个条件：一是最优子结构——dp[i]可以由dp[i-1]和dp[i-2]推出来；二是无后效性——一旦dp[i]确定了，后面的计算不需要关心你是怎么爬到第i阶的。

无后效性这个概念容易被忽略，但它很关键。举个例子，如果问题变成“爬楼梯，但不能连续跨两阶”，那dp[i]就不能只由dp[i-1]和dp[i-2]推出来了，因为你还得知道“到达第i-1阶时最后一步是跨了一阶还是两阶”。这时候状态就得扩展成dp[i][0]和dp[i][1]，分别表示“到达第i阶且最后一步跨了一阶”和“到达第i阶且最后一步跨了两阶”。

我踩过的一个典型坑是：状态定义得太粗，导致转移时信息不够用。比如有一道题是“打家劫舍”，你是一个小偷，不能偷相邻的两家。一开始我把状态定义成“偷到第i家时的最大金额”，但转移时发现没法判断第i-1家有没有偷。后来改成dp[i]表示“考虑前i家能偷到的最大金额”，转移时分两种情况——偷第i家（那第i-1家不能偷，金额是dp[i-2]+nums[i]）和不偷第i家（金额是dp[i-1]），取较大值。这样状态就够用了。

3.2 转移方程的推导：从“最后一步”倒着想

转移方程的推导有一个很实用的技巧：考虑最后一步做了什么选择。比如背包问题，最后一步要么选了第i个物品，要么没选；比如最长递增子序列，最后一步要么把当前元素接在某个子序列后面，要么自己单独成一个子序列。

以0-1背包为例：有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，每个物品只能选一次，求最大价值。状态定义为dp[i][j]表示“考虑前i个物品，容量为j时的最大价值”。考虑第i个物品的选择：

• 不选第i个物品：dp[i][j] = dp[i-1][j]
• 选第i个物品（前提是j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

两者取较大值，转移方程就是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

这个推导过程很自然，关键是把“最后一步的选择”想清楚。我习惯在草稿纸上画一个表格，行是物品编号，列是容量，然后手动填几行，看看转移关系对不对。这个笨办法看起来低效，但能帮你快速验证状态设计是否合理。

3.3 边界条件：最容易翻车的地方

转移方程写对了，边界条件没处理好，照样WA。边界条件包括两部分：初始状态和非法状态。

初始状态是递推的起点。比如背包问题里，dp[0][j] = 0表示“不考虑任何物品时价值为0”，dp[i][0] = 0表示“容量为0时价值为0”。这些看起来理所当然，但漏掉一个就可能出问题。

非法状态是指那些在转移过程中出现但实际无意义的状态。比如在背包问题里，j-w[i]可能小于0，这时候“选第i个物品”这个选项就不存在，不能参与max比较。很多人在写代码时忘了判断这个条件，导致数组越界或者取到错误的值。

还有一个常见的坑是初始化成负无穷还是0。如果问题求最大值，且某些状态不可达，那不可达的状态应该初始化为负无穷，否则会被错误地当成合法状态参与转移。比如“凑零钱”问题，求凑出金额n所需的最少硬币数，如果某个金额凑不出来，应该标记为无穷大而不是0，否则会被误认为“0个硬币就能凑出”。

4. 经典模型拆解：把套路变成直觉

4.1 线性DP：最长递增子序列的两种解法

最长递增子序列（LIS）是线性DP的经典问题：给定一个数组，求最长递增子序列的长度。子序列不要求连续，但要求保持原顺序。

第一种解法是O(n^2)的DP。状态定义：dp[i]表示“以第i个元素结尾的最长递增子序列长度”。转移时，遍历所有j < i，如果nums[j] < nums[i]，就可以把nums[i]接在nums[j]后面：

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

这个解法的时间复杂度是O(n^2)，空间O(n)。思路很直观，但数据规模大时会超时。

第二种解法是O(n log n)的贪心+二分。维护一个数组tails，tails[k]表示“长度为k+1的递增子序列的末尾元素的最小值”。遍历每个元素时，用二分查找在tails中找到第一个大于等于当前元素的位置，替换它；如果当前元素比所有tails元素都大，就追加到末尾。

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

这个解法的核心洞察是：为了让递增子序列尽可能长，末尾元素越小越好。tails数组本身是递增的，所以可以用二分查找。我第一次看到这个解法时觉得很神奇，后来想明白了——它其实是在维护“每种长度的最优结尾”，本质上还是一种DP思想的优化。

4.2 区间DP：戳气球的遍历顺序为什么重要

区间DP的典型特征是状态定义在区间上，转移时枚举区间的分割点。经典问题是“戳气球”：有n个气球，每个气球上有数字，戳破第i个气球获得的分数是nums[i-1] * nums[i] * nums[i+1]（相邻气球上的数字乘积），求戳破所有气球能获得的最高分数。

这个问题的难点在于：戳破一个气球后，左右两边的气球会变成相邻的，后续的分数计算会受影响。如果正着想，你没法确定戳破顺序。但倒着想就豁然开朗了——考虑最后戳破的那个气球。假设最后戳破的是第k个气球，那么在戳它之前，左边[0, k-1]和右边[k+1, n+1]的气球都已经戳破了，第k个气球的左右邻居是0号气球和n+1号气球（可以假设边界各有一个值为1的虚拟气球）。

状态定义：dp[i][j]表示“戳破区间(i, j)内所有气球能获得的最高分数”（注意是开区间，i和j不戳）。转移时枚举最后戳破的气球k：

dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])

遍历顺序很关键：必须按区间长度从小到大遍历。因为dp[i][j]依赖比它短的区间dp[i][k]和dp[k][j]。如果按i从小到大遍历，计算dp[i][j]时dp[k][j]可能还没算出来。我一开始没注意这个顺序，结果答案全是错的，调试了半天才发现问题。

def max_coins(nums): nums = [1] + nums + [1] n = len(nums) dp = [[0] * n for _ in range(n)] for length in range(2, n): for i in range(n - length): j = i + length for k in range(i + 1, j): dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]) return dp[0][n-1]

4.3 状态压缩：滚动数组把空间砍到极致

很多DP问题的状态转移只依赖前一层，这时候可以用滚动数组把二维DP压缩成一维，空间复杂度从O(n^2)降到O(n)。

以0-1背包为例，原始转移方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。注意到dp[i]只依赖dp[i-1]，所以可以把第一维去掉，用一维数组dp[j]表示“容量为j时的最大价值”。但这里有个陷阱：内层循环必须从大到小遍历。

为什么？因为dp[j]依赖dp[j-w[i]]，如果从小到大遍历，dp[j-w[i]]可能已经被当前物品更新过了，相当于同一个物品被选了多次，那就变成了完全背包。从大到小遍历可以保证dp[j-w[i]]还是上一轮的值，即“没选当前物品”的状态。

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

这个“从大到小”的细节我见过太多人搞错，包括我自己。有一次面试，面试官让我写0-1背包，我写完后面试官问“内层循环为什么从大到小”，我一时没答上来，场面很尴尬。后来才想明白，这背后是“每个物品只能用一次”这个约束在起作用。

5. 刷题路上绕不开的五个坑

5.1 把DP当贪心写：局部最优不等于全局最优

贪心和DP长得有点像，都是做选择，但贪心只考虑当前最优，DP会考虑所有可能的选择。有些题看起来可以用贪心，实际上必须用DP。

比如“零钱兑换”问题：给定不同面额的硬币和一个总金额，求凑出总金额所需的最少硬币数。如果硬币面额是[1, 5, 11]，要凑15，贪心会先选11，再选4个1，总共5枚硬币。但最优解是选3个5，总共3枚硬币。贪心在这里失效了，因为选11虽然当前看起来“最大”，但导致后续只能用1来凑，反而更差。

DP的解法是枚举所有硬币，取最小值：

def coin_change(coins, amount): dp = [float('inf')] * (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) return dp[amount] if dp[amount] != float('inf') else -1

判断一道题能不能用贪心，关键看“局部最优选择是否一定导致全局最优”。如果不确定，老老实实用DP。

5.2 遍历顺序搞反：背包问题从大到小的秘密

前面已经提到了0-1背包内层循环从大到小的原因，这里再展开说一下完全背包的对比。完全背包里每个物品可以选无限次，转移方程是dp[j] = max(dp[j], dp[j-w[i]] + v[i])，内层循环从小到大遍历。因为从小到大遍历时，dp[j-w[i]]可能已经被当前物品更新过，相当于允许同一个物品被多次选择。

这个区别可以用一个表格总结：

我建议在写背包问题时，先在草稿纸上手动模拟一遍小规模数据，确认遍历方向对不对。这个习惯帮我避免了很多低级错误。

5.3 边界条件漏写：数组越界和初始值错误

边界条件的问题五花八门，我列几个最常见的：

• 数组越界：转移时访问dp[i-1]或dp[j-w[i]]，但i=0或j<w[i]时越界。解决办法是在循环里加判断，或者把dp数组多开一位。
• 初始值错误：求最大值时初始化为0没问题，但求最小值时初始化为0会导致错误结果，应该初始化为无穷大。
• 返回值错误：有时候答案是dp[n]，有时候是max(dp)，取决于状态定义。比如LIS问题，dp[i]表示“以第i个元素结尾的LIS长度”，答案是max(dp)而不是dp[n-1]。

5.4 空间优化过头：滚动数组用错方向

滚动数组是个好东西，但用错了方向比不用还糟糕。除了背包问题的从大到小，还有一些场景需要注意。比如二维DP压缩成一维时，如果转移依赖dp[i-1][j-1]和dp[i-1][j]，那内层循环的方向取决于具体依赖。一般来说，如果dp[j]依赖dp[j-1]（即同一层的左边），那内层循环要从大到小；如果依赖dp[j+1]（同一层的右边），那要从小到大。

我个人的习惯是：先用二维DP把答案跑通，确认逻辑正确后，再尝试压缩空间。压缩后用小规模数据对比二维版本的结果，确保一致。

5.5 状态定义太粗：信息不够导致转移失败

前面打家劫舍的例子已经说明了这个问题。再举一个例子：股票买卖问题，限制最多交易k次。如果状态只定义dp[i]表示“前i天能获得的最大利润”，那转移时没法知道已经交易了几次。正确的状态定义是dp[i][k][0/1]，表示“第i天，最多交易k次，当前持有/不持有股票时的最大利润”。

状态定义的粒度需要根据问题的约束来定。约束越多，状态维度越高。但维度太高会导致时间和空间爆炸，所以需要在“信息够用”和“复杂度可控”之间找平衡。这也是DP问题最考验功力的地方。

6. 从会做到做快：我的DP练习方法

6.1 按模型分类刷，不要按题号顺序刷

我刚开始刷题时是按题号顺序刷的，结果刷了50道题，遇到新题还是不会。后来改成按模型分类刷，效果好了很多。DP的常见模型就那么几类：线性DP、区间DP、背包DP、树形DP、状态压缩DP、数位DP。每类模型集中刷10到15道题，把这类题的套路吃透，再刷下一类。

比如背包DP，先把0-1背包、完全背包、多重背包、分组背包这几个变种搞清楚，再刷“零钱兑换”“分割等和子集”“目标和”这些应用题。刷完之后你会发现，很多题本质上就是背包问题的马甲。

6.2 每道题都问自己三个问题

我现在做DP题时，会强迫自己回答三个问题：

1. 状态是什么？用一句话说清楚dp[i]或dp[i][j]代表什么。
2. 转移方程是什么？考虑最后一步的选择，写出递推式。
3. 边界条件是什么？初始状态怎么定义，哪些状态不可达。

这三个问题回答清楚了，代码基本就是翻译。如果有一个问题答不上来，说明还没想透，继续想。

6.3 用暴力递归验证DP的正确性

DP写完之后，我习惯写一个暴力递归版本，用小规模随机数据对拍。暴力递归虽然慢，但逻辑简单，不容易出错。如果两个版本的结果一致，那DP大概率是对的。

import random def brute_force(nums): # 暴力递归版本 pass def dp_solution(nums): # DP版本 pass for _ in range(1000): n = random.randint(1, 10) nums = [random.randint(1, 100) for _ in range(n)] assert brute_force(nums) == dp_solution(nums), f"Failed on {nums}"

这个对拍方法帮我抓出了很多隐蔽的bug，尤其是边界条件的问题。

6.4 画表格手动模拟，比盯着代码看管用

DP的转移过程是抽象的，光看代码很难发现逻辑错误。我的习惯是画一个表格，手动填几行数据，看看状态转移是否符合预期。比如背包问题，画一个(n+1) x (C+1)的表格，行是物品，列是容量，手动填前几行，观察dp[i][j]的值是否合理。

这个办法看起来笨，但非常有效。很多时候，手动模拟到某一步就会发现“这里怎么算出来是负数”或者“这个状态不应该可达”，然后就能定位到问题。

6.5 定期回顾错题，建立自己的DP模板库

我维护了一个错题本，记录每道做错的DP题、错误原因、正确思路。每隔一段时间回顾一次，看看哪些错误是反复犯的。比如我发现自己经常在“遍历顺序”上出错，就专门整理了一份遍历顺序的检查清单，每次写DP前对照检查。

另外，我还整理了一些常用DP模型的代码模板，比如背包问题的几种写法、LIS的两种解法、区间DP的遍历框架。这些模板不是用来背的，而是用来参考的——写题时如果卡住了，看一眼模板找找灵感。

动态规划的学习曲线确实比较陡，但一旦跨过那个坎，你会发现很多问题都能用DP的思路去拆解。我自己的体会是：DP不是靠天赋，而是靠积累。每道题都是一次状态设计和转移推导的练习，刷得多了，看到新题时脑子里自然就会浮现出类似的模型。刚开始可能要想很久才能定义出状态，后来可能几分钟就能找到思路。这个从慢到快的过程，本身就是一种动态规划——把每次解题的经验存起来，避免重复踩坑，最终拼出属于自己的算法能力。