企业官网建设流程全解析

很多人学动态规划，第一轮啃概念，觉得“最优子结构、无后效性、重叠子问题”说得头头是道，合上书就废。真正拿到一道新题，状态定义想一小时，转移方程憋不出来，边界条件一写就错。这篇《动态规划理论基础II》不打算再抄一遍教材，而是想把理论和实操中间那层断层补上：状态到底怎么定义、转移方程怎么推、经典模型怎么归类、出了问题怎么调。适合的读者是已经大概知道DP是什么、但做题还经常卡壳的人。如果你是零基础，建议先去把递归、记忆化搜索和斐波那契这类例子弄熟，再回来看这篇。

很多人以为DP难在转移方程，其实我刷了这么多题之后的感觉是，90%的卡壳都出在状态定义上。状态是动态规划的地基，地基歪了，后面全是空中楼阁。这篇我会用大量具体例子，把我平时做题时的思考过程直接摆出来，尽量不写一句正确的废话。

1. 状态设计：动态规划真正难住人的第一步

1.1 状态定义的本质：你在为子问题拍一张快照

状态到底是什么？我的理解是：状态是你对某个子问题的一个“快照”，它用几个参数把解决这个问题所必须知道的信息浓缩起来，结果值就是这个快照对应的最优答案。为什么要这么想？因为动态规划本质上是对递归搜索的缓存，只有参数完全相同的子问题才能共用缓存。所以状态定义的第一原则是：参数要包含“未来决策所需的全部信息”，同时又尽量少带无关信息。

拿最长上升子序列来举例。假设我想定义dp[i]表示“前i个元素的最长上升子序列长度”，够不够？不够。原因是后面元素能不能接上，取决于当前子序列的末尾值是多少，而“前缀的最长值”不一定是“尾巴最有机会接新元素”的那一个。比如数组是[2, 5, 3, 7, 4]，只看前3个元素，最长上升子序列是[2, 5]，长度2，以3结尾的子序列是[2, 3]，长度也是2。但后面的4能接在3后面，却不能接在5后面。如果状态里不记录“以谁结尾”，这个信息就丢了。所以更准确的状态是dp[i]：以第i个元素结尾的最长上升子序列长度，答案是对所有dp[i]取最大值。

这个例子的价值在于它展示了一个思考模板：每次写状态之前，问自己一句“决策最后一步的时候，我需要知道关于之前的哪些信息？”。需要知道处理到哪个位置，这是一个维度；需要知道当前结尾的值、剩余容量、已用次数，这些是追加的维度。额外维度不是拍拍脑袋加上去的，而是为了保证无后效性——所有会影响未来决策的信息，都必须收进状态里。

1.2 从题目条件反推状态要有几维

我刚开始学DP的时候，最喜欢猜状态，看到数字就写dp[n]，结果经常把一维用到底。后来养成一个习惯：先看输入参数的数量。如果输入只有一个序列，状态通常至少一维；如果输入里有一个容量、一个上限、一个次数约束，你就要认真考虑是不是该再加一维。因为状态维度的本质，就是递归搜索树上一个节点需要记录哪些参数。

举个例子，0-1背包问题：N个物品，每个物品有重量wi和价值vi，背包容量W，求能装下的最大价值。搜索树上一个节点需要知道两件事：当前处理到第几个物品了，包里还剩多少容量。这就是二维状态dp[i][j]，表示前i个物品里选一些放进容量j的包能拿到的最大价值。同样的题目，如果加一个限制“总共最多选K个物品”，那必须再开一维变成dp[i][j][k]，表示前i个物品、用了j容量、已经挑了k个物品时的最大价值。规律很简单：多一个会被限制的条件，通常就多一维状态。

不过也要提醒一句，状态维度不是越大越好。每多一维，时间和空间可能就多一个数量级。真正见功夫的是信息压缩：题目里每个物品有编号，但背包问题根本不需要知道选的是哪几个，只需要知道考虑了多少个、用了多少容量。把“具体集合”压缩成“已考虑的个数”，这就是从指数级搜索降到多项式DP的关键。

2. 转移方程是怎么一步一步推出来的

2.1 永远先想“最后一步”是什么

转移方程不是灵光一现，它描述的是：当前这个状态，可以从哪些前驱状态通过一次决策到达。我自己的习惯是“以终为始”——不要从dp[1]开始想递推到dp[n]，而是反过来想，假设当前状态已经算好了，它的值是从哪些来源拼出来的。

一维爬楼梯是最简单的示范。要到第n阶，最后一步只能是从n-1阶迈一阶，或者从n-2阶迈两阶。这两个来源互斥且完备，所以dp[n] = dp[n-1] + dp[n-2]。这个例子太简单，但思路通用。

再看一个稍微有味道的题，零钱兑换：给定总额amount和硬币面额数组coins，求凑出这个总额最少需要几枚硬币。凑出x元，最后一步必然是选择一枚面额为c的硬币，那么前一个状态就是“凑x-c元”。把所有c都枚举一遍取最小，得到：

dp[x] = min(dp[x - c] for c in coins) + 1

这里的前驱不是固定的一个，而是一组候选，由最后一个决策决定。这正是转移方程最常见的形态：枚举最后一步的所有可能，从各个前驱状态取最优或求和。

最长上升子序列也一样。dp[i]表示以第i个元素结尾的LIS长度，那么倒数第二个元素是某个下标j，必须满足j < i且nums[j] < nums[i]。于是：

dp[i] = max(1, max(dp[j] + 1 for j in range(i) if nums[j] < nums[i]))

所有转移方程，本质上都在做同一件事：枚举“从哪个状态来”。你把这个逻辑想通了，就不再需要背任何DP模板。

2.2 边界条件与循环顺序：两个让人头大的细节

边界条件写不对，大概率是没想清楚“空状态”的含义。我的经验是，不要把所有dp都统一初始化成0，必须先明确每个格子代表的是“合法状态”还是“不可达状态”。求最大值时，不可达状态常设成负无穷或-1；求最小值时，不可达状态常设成正无穷；只有真正可以当作起点的状态才单独初始化成0、1或其他具体值。

举一个典型的反例。求最少跳跃次数到达数组末尾，如果你把所有dp初始化为0，转移时做min操作，那么所有状态都会从0这个“假合法”状态取到最小值，答案永远是0。正确做法是把dp[0]初始化为0，其余初始化为很大的数，比如float('inf')，然后当某个状态能从更少步数的合法状态跳过来时才更新。这层理解比背“初始化为INF”更重要。

循环顺序也一样。动态规划本质上是在一张有向无环图上按拓扑序填表，一个状态依赖谁，就要保证在计算它之前，被依赖的格子已经被填好。爬楼梯从2到n正着循环，因为dp[i]依赖dp[i-1]和dp[i-2]；有些倒推问题，依赖dp[i+1]，那就要从n-1到0倒着循环。区间DP必须外层按区间长度枚举，因为长区间依赖短区间；0-1背包必须容量倒序枚举，因为要避免当前物品被重复使用。这些都不是需要死记的口诀，而是“依赖先算好”的自然结果。

3. 三大经典模型背后的统一逻辑

3.1 背包模型：容量与价值之间的权衡

背包问题之所以经典，是因为它抽象了一大类资源分配问题：手里有总量有限的资源，一大堆候选项目各有代价和收益，怎么选收益最大。0-1背包、完全背包、多重背包的区别，本质只是每个物品能用几次。

0-1背包的转移很多人都会写：

for i in range(1, n + 1): for j in range(capacity, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

这里dp[j]表示容量为j时能拿到的最大价值。为什么要倒序枚举容量？因为正序的话，你计算dp[j]时读到的dp[j - weight[i]]可能已经被这一轮外层循环更新过了，它已经包含了“选入第i个物品”的结果，于是同一轮里你能把同一个物品塞进去两次。倒序能保证读到的永远是上一层的老值，也就是说每件物品最多被选一次。

完全背包和0-1背包的转移几乎一样，唯一的区别是内层循环改成正序：

for j in range(weight[i], capacity + 1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

用刚才的逻辑解释就通了：正序循环时，dp[j - weight[i]]可能是刚刚被本轮更新过的新值，它已经包含了使用第i个物品的可能，所以一个物品可以被反复使用，正好符合“无限量供应”的语义。你看，根本不用背哪个背包正序哪个倒序，把覆盖顺序想明白就行了。

多重背包是另一个故事。每个物品最多用cnt次，朴素做法是再加一层循环枚举使用次数，复杂度直接乘上一个k。经验做法是二进制拆分：把cnt拆成1、2、4、8、……以及最后剩下的余数，每一份都当成一个独立的新物品，然后跑0-1背包。为什么可行？因为任何0到cnt之间的整数，都能由这些2的幂子集组合出来。这个办法理解了以后，竞赛里处理多重背包就很顺手。

3.2 区间DP：先合并小的，再合并大的

区间DP是另一类特别常见的模型，状态通常是dp[l][r]，表示对区间[l, r]做某种处理后的最优值。最经典的例子是石子合并：有一排石子堆，每次只能合并相邻两堆，代价是这两堆重量之和，问合并成一堆的最小总代价。

关键在于最后一步：整堆石头一定是由左右两部分合并来的，所以转移方程是枚举分界点k：

dp[l][r] = min(dp[l][k] + dp[k + 1][r] + sum(l, r) for k in range(l, r))

其中sum(l, r)是区间[l, r]的总重量，是最后一次合并付出的代价。代码结构基本固定：先枚举区间长度len，再枚举左端点l，算出右端点r = l + len - 1，最后枚举分界点k。三重循环，复杂度O(n^3)。为什么外层必须枚举长度？因为dp[l][r]依赖的所有子区间长度都小于len，只有按长度从小到大，才能保证需要的值都已经算好。

矩阵链乘问题也是同一个骨架，dp[l][r]表示第l个到第r个矩阵连乘的最少乘法次数，转移里多了一个维度参数p，代价是p[l-1] * p[k] * p[r]。很多看起来完全不同的题，比如戳气球、括号匹配、多边形剖分，最后都是这个模式。所以我建议你把区间DP的“长度-左端-分界点”三层循环写成肌肉记忆，在此基础上理解每道题自己的代价函数是什么。

3.3 状态机DP：把“当前处于什么阶段”写进状态

有些序列DP题，除了位置维度之外，还隐含一个“当前处于什么状态”的信息。最典型的就是打家劫舍：一排房子，不能偷相邻的两家，问最大收益。如果只定义dp[i]表示前i家的最大金额，你会发现转移很别扭，因为你不知道第i家到底偷没偷，也就不知道第i+1家能不能偷。解决方案是加一维：

dp[i][0] = max(dp[i-1][0], dp[i-1][1]) # 不偷第i家 dp[i][1] = dp[i-1][0] + nums[i] # 偷第i家

0表示“第i家没偷”，1表示“第i家偷了”。这个状态定义就是一个微型状态机，节点是0/1，转移边是“从某个状态走到另一个状态”。

股票买卖问题更好理解。每天结束时，你手里要么持有股票，要么不持有。dp[i][0]表示第i天结束时手上没有股票的最大现金，dp[i][1]表示第i天结束时持有股票的最大现金：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i])

持有状态可以继续持有，也可以卖掉变成不持有；不持有状态可以继续观望，也可以买入变成持有。限制“最多交易k次”时，再加一维k，买入动作消耗一次交易次数。状态机DP的价值在于：把题目里用自然语言描述的限制，显式地变成状态维度，之后转移就是单纯地在状态图上走边。这个思想再往前一步，还能处理允许冷却期、包含手续费等一系列股票衍生题。

4. 实战前必看：DP调试三板斧与常见错误速查

4.1 先判断能不能用DP：三个必要条件

很多人拿到题就开始写状态，其实第一步应该判断这题适不适合DP。三个必要条件是：最优子结构、重叠子问题、无后效性。最优子结构指原问题的最优解可以由子问题的最优解组装出来；重叠子问题指同一个子问题会被多个更大的问题反复使用；无后效性指一旦某个状态的值确定，后面怎么决策都不受到达该状态的具体路径影响。

用零钱兑换做例子很合适。硬币面额1、5、11，要凑15。如果贪心每次都拿最大的11，得到的是4枚硬币，但最优解是5+5+5，3枚。为什么贪心失效？因为局部最优推不出全局最优。DP能行，是因为“凑15的最少硬币数”可以由“凑14、凑10、凑4”这三个子问题各加1枚得到，子问题之间重叠且独立。这三条都满足，DP就是合适的工具。

如果问题有重叠子问题，但不存在最优子结构，那DP也未必成立。比如求最长简单路径，路径不能重复经过节点，子路径的最优选择会互相影响，这时候DP就失灵了。所以我的例行公事是：拿到题目先自言自语两句话——这个全局最优能不能拆成子问题最优？后面决策还需要知道前面哪些破事？如果都说得通，再动笔写状态。

4.2 调试DP三板斧

第一板斧是打表。写完转移方程，先输出整个dp数组或dp矩阵，逐行看。二维表就一张张打印，看哪些格子是无穷大、哪个格子是起点、每个格子是从哪个格子转移来的。很多时候你一眼就能看出“这个值是从一个不可能的状态推来的”。

第二板斧是造最小用例。n等于1、等于2、空数组、只有一堆石子，这些边界情况手算答案特别容易，跑完程序一对比就知道边界对不对。小数据错了，再用打表定位，效率极高。

第三板斧是暴力对拍。写一个纯递归或直接枚举所有方案的暴力方法，不关心复杂度，然后生成几十组n不超过8的小随机数据，把暴力结果和DP结果逐个比对。这个方法极其土，但极其有效。我个人的习惯是：每写一个DP题，只要不是考场赶时间，都会顺手写个暴力对拍。一旦发现结果不一致，打印DP表和暴力的搜索路径，几乎没有定位不了的问题。

4.3 常见错误速查表

表格最后再补一句我的体会：初值的本质是“这个状态下还没做任何决策时的信息”。求方案数，dp[0]常常等于1，因为凑出空集只有一种方案；求最少步数，dp[0]常常等于0，因为原地不用走；不可达状态设成极大或极小，是为了让min/max操作自动避开它。想明白这些，边界条件就不是靠猜了。

4.4 空间优化不是炫技，是必要的工程意识

当转移只依赖上一层的状态时，可以把二维数组压成两个一维数组，甚至一个数组。滚动数组最经典的应用就是背包空间优化，把dp[i][j]压成dp[j]，前提是循环方向正确，保证更新时读到的还是上一层的值。空间优化后，代码看起来更简洁，但对“什么时候覆盖旧值”的要求更高，所以我建议初学者先写二维版本，验证正确后再压维，不要上来就写滚动数组然后疯狂debug。

再往上走，还有状态压缩DP，用一个整数bitmask表示一个集合。比如旅行商问题，dp[mask][v]表示已经访问过的城市集合为mask，当前停在v点的最小花费。这类题的状态本身就是集合，维度拆不开，只能用mask压缩。这是理论基础的延伸方向，先知道有这个东西，等真正遇到再把bitmask的几个技巧捡起来。

回到开头的那个问题：动态规划的理论基础到底在讲什么？我现在的答案是，只讲两件事：状态里存什么，状态之间怎么走。状态设计回答前者，转移方程和循环顺序回答后者。这两件事想明白了，剩下的事情都可以靠调试和练习磨出来。

最后分享一个小经验，也是我用了很久都觉得很有效的习惯：拿到任何一道DP题，先在草稿纸上写三行注释——状态定义、转移方程、初始条件，然后才开始写代码。这个动作看着傻，但它能逼着你在动手之前把所有逻辑漏洞想清楚。动态规划不是靠灵感，靠的是把每一步都想明白的耐心。