企业官网建设流程全解析

你有没有发现，“DP”这个词最近在热搜榜上同时养着两拨人。一拨人在搜算法题解、学动态规划，另一拨人在找DP线材、看DisplayPort转Type-C的输出方案。巧了，我在评论区还见过一个段子：有人说自己学了三天DP，到头来发现买的是根视频线。如果你搜DP是为了找线，那现在可以退出去买线了；如果你是想搞懂算法里的动态规划，今天这篇应该能帮你把这条路走顺。

动态规划（Dynamic Programming）几乎是算法面试里最绕不开的一块硬骨头，也是很多人从“会写代码”到“会写算法”之间那道最明显的门槛。它既不像暴力搜索那样无脑，也不像贪心那样看运气，它是有一套完整方法论、但偏偏又最考验“设计感”的算法。我接触DP算起来也有七八年了，从大学被背包问题折磨到怀疑人生，到后来在竞赛里靠数位DP和区间DP拿分，再到现在面试别人时看候选人怎么定义状态——这条路我踩过的坑，应该值得你花点时间看看。

1. 动态规划到底解决什么问题：先把“动态”两个字忘掉

1.1 一个被名字误导的算法

我第一次接触动态规划的时候，被“动态”这两个字带偏了很久。我以为它是一种在运行中不断调整策略的算法，类似某种自适应控制、某种“动态”调整。事实证明完全不是那么回事。

动态规划本质上一点都不“动态”。它的核心是一张表、一套递推关系、一组边界条件。你把这些东西定义好之后，剩下的工作几乎是机械的、静态的。真正“动态”的，只是你在脑子里设计状态转移方程那个过程。一旦方程写出来，代码反而是所有算法里最好写的。

很多人学DP觉得难，难就难在它不像排序算法那样有个固定的代码模板。你背会快排就是快排，背会归并就是归并。但DP没有万能模板，它的模板是“方法论”：怎么定义状态，怎么写转移，怎么定边界。这三个问题换一道题就是一个新解法，所以很多人觉得DP像玄学，实际上是你还没抓到那根主线。

1.2 动态规划的两个底层前提：重叠子问题和最优子结构

在聊具体解法之前，我先说两个几乎所有DP题都逃不开的前提，理解了这两个东西，你对DP的认知会清楚一大半。

第一个叫重叠子问题。举个例子，斐波那契数列你递归算F(10)，你得先算F(9)和F(8)；算F(9)你要算F(8)和F(7)。这个过程中F(8)被重复拆解了无数次。如果你用一个数组把每次算出来的结果存下来，下次直接用，这就是记忆化搜索，也就是自顶向下的DP。如果你反过来，从F(0)、F(1)一路递推到F(10)，这就是自底向上的递推，也就是我们最常见的DP写法。两条路本质相通。

第二个叫最优子结构。意思是：一个问题的最优解，可以由它的子问题的最优解组合出来。比如你要算从第1层爬到第10层有多少种爬法（每次爬1层或2层），第10层的答案是第9层的答案加上第8层的答案，因为最后一步要么从第9层跨1层过来，要么从第8层跨2层过来。这背后就是最优子结构在起作用。

1.3 用爬楼梯的例子把DP讲“破”

说个谁都听过的例子：爬楼梯。有n级台阶，每次可以跨1级或2级，问有多少种不同方式爬到顶。

不用DP的写法是纯递归：F(n) = F(n-1) + F(n-2)。看着简洁，但你稍微算一下就会发现复杂度是O(2^n)，n=45的时候你电脑已经跑不动了。问题就出在大量重复计算上。

用DP的思路，你只要开一个数组dp，让dp[0] = 1（站在地面算1种方式），dp[1] = 1（一级台阶1种方式），然后从2到n循环：dp[i] = dp[i-1] + dp[i-2]。循环结束输出dp[n]。

就这么简单。这个例子的价值是让你直观感受到：DP就是把一个看起来需要递归拆到底的问题，变成一张从前往后填的表。你不再重复计算任何东西，每个子问题只算一遍。复杂度从指数级降到线性级，这就是DP最原始、最核心的威力。

注意：很多教材喜欢把dp[0]定义为1，理由是“原地不动是一种方案”。你如果不习惯，也可以把dp[1]=1、dp[2]=2作为初始条件，然后从3开始循环。两种做法都对，关键是你自己心里要有一致性，别混着用。

2. 动态规划解题五步法：从题意到递推式的最短路径

2.1 五步法的具体拆解

我自己带过不少新人，发现大家面对DP题最大的困惑不是代码写不出来，而是“不知道从哪开始想”。后来我把自己的思考过程总结成五步，按顺序走一遍，大部分中等难度的DP题都能解出来：

1. 定义状态。用一个或多个维度描述“我已经处理到哪一步、当前处于什么情况”。这一步是DP的灵魂，定义得好，后面全是顺水推舟；定义得差，后面怎么调都是歪的。
2. 写出状态转移方程。搞清楚“当前状态能从哪些之前的状态转移过来”，一般就是枚举最后一个动作。
3. 确定初始化。边界状态的值必须符合实际含义，这一步错，整张表都是错的。
4. 确定遍历顺序。要保证算dp[i]的时候，它依赖的dp[j]都已经算过了。
5. 用小例子手动推演一遍。拿个n=3或n=4的小样例，自己拿笔画一遍，确认转移方程不会越界、不会漏情况。

这五步里，前四步是硬功夫，第五步是大多数人偷懒跳过然后翻车的坑。你别嫌麻烦，遇到新题先拿小数据手推，比自己盲改代码快得多。

2.2 一个完整的实战案例：最长上升子序列（LIS）

光说不练假把式，拿一个面试高频题“最长上升子序列”看五步法怎么落地。题目是：给定一个无序数组，例如[10, 9, 2, 5, 3, 7, 101, 18]，找出其中最长的严格上升子序列的长度。注意子序列不要求连续，但相对顺序不能变。

按五步走：

第一步，定义状态。我选dp[i]表示“以第i个元素结尾的最长上升子序列长度”。这个定义很关键，因为如果不要求“以第i个结尾”，后面就很难写转移。

第二步，写转移方程。dp[i] = max(dp[j] + 1)，其中0 <= j < i，且nums[j] < nums[i]。意思是我把nums[i]接到某个比它小的数字后面，长度就在那个数字的dp值基础上加1；也可以不接任何人，自己单独作为一个子序列，所以dp[i]至少是1。

第三步，初始化。每个元素的dp值初始都是1，因为每个元素自身就是一个长度为1的上升子序列。

第四步，遍历顺序。i从左到右，j从0到i-1，保证算dp[i]时所有dp[j]已知。

第五步，手推。数组[10, 9, 2, 5]：dp[0]=1；9比10小，dp[1]=1；2比谁都小，dp[2]=1；5前面比它小的只有2，dp[3]=dp[2]+1=2。答案取max(dp)。逻辑没错。

def length_of_lis(nums): if not nums: return 0 n = len(nums) 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)

这个写法时间复杂度O(n^2)，在n=1000以内的题目完全够用。如果想更快，可以再用一个数组维护“当前长度对应的最小结尾”，配合二分查找把复杂度降到O(n log n)，这个属于进阶优化，后面会讲。

2.3 为什么很多人学DP“一看就会，一写就废”

我见过太多人学DP的路径是：看题解，觉得秒懂，关上题解，写不出来，再看题解，恍然大悟，上了考场，还是不会。这不是你笨，是学习方法出了问题。

问题出在你看题解的时候，跳过了最核心的“状态定义”环节，直接看了答案。你记住了这道题的方程，却没记住这道题是怎么想到这个状态、为什么这么定义。下次题目换个包装，你就认不出来了。

我的建议是：刷DP题的时候，先别看题解的前半部分，只看题目，逼自己想状态定义。想不出来可以看提示，但看完提示一定要问自己一句：为什么这个状态是对的？它覆盖了所有可能在“最后一个动作”上发生的情况吗？这才是把DP真正学进脑子里的方式。

3. 五大经典DP模型拆解：背包、序列、区间、数位、状压树形

3.1 背包问题：01背包与完全背包

背包问题绝对是DP里的第一大门派，面试八股和竞赛入门都绕不开。01背包的问题描述是：有n件物品，每件物品有重量w[i]和价值v[i]，背包容量是C，问能装下的最大价值是多少。每件物品最多选一次。

标准状态定义是dp[i][j]表示“从前i件物品中选，总重量不超过j时的最大价值”。转移方程是：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。意思就是面对第i件物品，要么不装，要么装。如果装，那之前i-1件物品只能用掉j-w[i]的容量。

这里有一个非常经典、也是面试官最爱问的细节：用滚动数组优化成一维dp[j]时，j要倒着遍历。为什么？因为一维数组里dp[j-w[i]]必须是“上一轮、还没被本轮更新过”的值，如果j从小到大遍历，dp[j-w[i]]可能已经被本轮前面的循环覆盖成新值了，那你就等于允许了一件物品被选多次，01背包就退化成完全背包了。倒着遍历则保证dp[j-w[i]]还是旧的。

# 01背包，一维滚动数组，容量j倒序遍历 for i in range(n): for j in range(C, w[i] - 1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i])

而完全背包（每件物品可以选无限次）恰好相反，j要正序遍历，这样dp[j-w[i]]会被本轮更新覆盖，天然实现了“可以重复选”。两个背包唯一的区别就在这一行遍历顺序上，很多人笔试时一紧张就写反，这里一定要刻进DNA。

3.2 序列类DP：最长公共子序列与编辑距离

序列类DP的套路是“两个序列就开二维表”。最长公共子序列（LCS），dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。转移分两种情况：如果A[i-1]等于B[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1；如果不相等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

还有一种更进阶的序列DP是编辑距离，就是算把一个字符串变成另一个字符串最少需要多少次操作（增、删、改各算一次）。dp[i][j]仍然表示A的前i个字符变成B的前j个字符的最小代价。转移方程稍微复杂一点点：

if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j] + 1, # 删除a[i] dp[i][j - 1] + 1, # 在a中插入b[j] dp[i - 1][j - 1] + 1) # 把a[i]替换成b[j]

这类题目最容易错的地方是初始化。dp[0][j]必须等于j，因为空字符串要变成B的前j个字符，只能靠插入j次；dp[i][0]必须等于i，因为A的前i个字符要变成空串，只能靠删除i次。这个初始化的意义在于：它给整张表的边界铺好了地基，地基歪了，后面全歪。

3.3 区间DP：合并石子与矩阵链乘

区间DP是另一种经典模型，特征是“在一个区间上进行合并或划分”。最典型的例子是石子合并：有几堆石子排成一排，每次只能合并相邻两堆，代价是两堆石子的重量之和，问把所有石子合并成一堆的最小总代价。

状态定义是dp[i][j]表示合并从i到j这一整段石子的最小代价。转移时枚举一个分割点k，把区间[i,j]分成[i,k]和[k+1,j]两段，分别合并后再把两堆合成一堆，代价加上这段的总重量：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，其中k从i到j-1。

区间DP有个特别的遍历顺序，不是从1到n从外到内，而是按区间长度从小到大去填表。先算长度为1的（不用合并，代价是0），再算长度为2的、3的……一直到整个区间。顺序错了，你会发现自己算一个长区间时，依赖的短区间还没填好。

这类题容易踩的坑是状态定义里漏掉“相邻”这个条件。有些DP题是允许从任意堆之间合并的，那用贪心或者堆就能解；一旦要求只能合并相邻，就必须用区间DP。看到“相邻”两个字，优先往区间DP上想。

3.4 数位DP：统计问题的高效解法

数位DP是很多人觉得“太玄”的一类题，但它的本质其实就是DFS加记忆化。它解决的问题长这样：给定一个区间[L, R]，统计这个区间内满足某个条件的数的个数。比如“数字中不含4”“数字中连续两位不能是……”。

套路是先把区间查询转化成F(R) - F(L-1)的形式，然后写一个dfs(pos, status, limit)。pos表示当前处理到第几位；status表示当前已经携带的信息，比如上一位数字是几、当前是否已经进入了合法状态；limit表示当前位是否被上限数字约束。如果limit为False，意味着这一位可以随便填0到9，那么后面所有情况的数量是固定的，可以直接用记忆化缓存。

# 数位DP的通用框架（伪代码） def dfs(pos, status, limit): if pos == n: return 1 if is_valid(status) else 0 if not limit and memo[pos][status] != -1: return memo[pos][status] up = digits[pos] if limit else 9 ans = 0 for d in range(0, up + 1): ans += dfs(pos + 1, new_status(status, d), limit and d == up) if not limit: memo[pos][status] = ans return ans

很多新手第一次看数位DP会问：为什么要limit这个参数？因为上限数字的约束是动态的。比如统计[1, 321]时，如果百位取了2，那十位最大可以到9；如果百位取了3，那十位最大只能是2。limit就是用来标记“当前这位有没有被上限压着”的。

数位DP的难点在于status的设计，它高度依赖题目条件。这部分没有太多模板可套，需要多刷几道题积累手感。但框架是固定的，你把这个dfs模板背熟，遇到统计数字个数的题至少有一个下手方向。

3.5 状态压缩DP与树形DP：进阶必备

状态压缩DP，简单说就是把一个集合的取舍状态用一个整数的二进制位来表示。最经典的例子是旅行商问题（TSP）：有n个城市，两两之间有距离，问从起点出发走完所有城市再回来，最短路径是多少。dp[mask][i]表示“已经访问过的城市集合是mask，当前停留在城市i”的最短路径长度。mask是一个整数，它的第k位是1代表第k个城市已经访问过了。

转移就是枚举下一个要去的城市j：dp[mask | (1 << j)][j] = min(dp[mask][i] + dist[i][j])。状态压缩DP的数据范围一般很小，n通常在20以内，因为2^20大约是一百万，再大就存不下了。

树形DP则是把DP建立在树的遍历上，特征是要算“根节点的答案”得先知道“所有子节点的答案”，所以一般用DFS后序遍历。经典题是“没有上司的舞会”：每个员工有快乐值，如果选了这个人，他的直接下属就不能选；如果不选他，下属可选可不选。需要dp[node][0]和dp[node][1]两个状态，分别表示以node为根的子树里，不选/选node能获得的最大快乐值。

树形DP写起来套路感很强，本质上就是DFS里做一次聚合。我第一次写树形DP的时候，觉得它像“在树上跑一个后序的01背包”，这个类比一直用到现在，还是很贴切。

4. 区分DP和贪心、分治、递归：别再傻傻分不清

4.1 四张脸谱放在一起对比

我经常在面试里问候选人：贪心和DP都能求最优解，区别在哪？好多人答不上来。我后来习惯用一张表把四个“长得像”的算法分开：

分治和DP最本质的区别就是子问题重不重叠。归并排序的左半部分和右半部分完全不相干，各排各的；而斐波那契的F(8)是F(9)、F(10)重叠依赖的。所以归并排序不需要记忆化，DP必须记忆化。

4.2 怎么判断一道题该用DP还是贪心

判断标准就一个词：后效性。简单说，就是你这一步的选择，会不会影响后续可选的决策空间？如果不会，贪心大概率够用；如果会影响，请老老实实上DP。

举两个对比鲜明的例子。“跳跃游戏2”：给定数组，每个元素代表你在该位置最多能跳多远，求用最少步数跳到最后一个位置。这题的标准解法是贪心，因为你在当前位置选择“跳到下一个能跳更远的点”，这个决策并不会毁掉未来的选择空间，每步都是当前最优。但如果加一个限制，比如不同位置有不同的跳转花费，那贪心就废了，必须DP。

4.3 无后效性：DP状态设计的“上帝视角”

DP为什么能保证全局最优？靠的就是无后效性，也叫马尔可夫性——某个阶段一旦确定，之后的发展不受这个阶段之前各阶段的影响。翻译成人话就是：dp[i]一旦算出来，后面要用它的时候，你完全不需要关心dp[i]是怎么算出来的，只需要用它的值。

这个性质对状态设计有很强的指导意义。你定义状态时，必须保证当前状态已经“封存”了所有将来需要的信息。如果算完dp[i]之后，后面还需要知道“i之前某个具体选择了什么”，那说明你的状态定义漏信息了，要额外加维度。

5. DP超时超内存怎么办：四大优化套路盘点

5.1 滚动数组：空间不够的救法

很多DP方程里，dp[i]只依赖dp[i-1]或者dp[i-1]和dp[i-2]，那就不需要保留整个二维数组，只要开两行或者几个变量滚动使用。斐波那契数列就是最极端的例子，全程只需要两个变量，不需要数组。

a, b = 0, 1 for _ in range(n): a, b = b, a + b

区间DP里也经常用滚动，不过要注意：如果状态依赖的是整个dp[i][k]的一部分（比如依赖同行的多个位置），滚动数组就需要小心覆盖顺序。安全起见，先确认依赖关系，再决定滚动方向。

5.2 状态压缩：二维压一维

这个在01背包里已经提过了。二维dp[i][j]压成一维dp[j]，关键在于遍历顺序和原始二维表保持语义一致。这类优化不仅省空间，写起来也更快，是实战中最常用的优化手段。

再补充一个例子：LCS的滚动数组。LCS其实只需要上一行的信息，所以可以用dp[2][j]交替存储，空间从O(n*m)降到O(m)。竞赛里如果题目数据范围大得离谱，这个优化经常能救你一命。

5.3 二分优化与数据结构优化

LIS可以用贪心加二分做到O(n log n)。思路是维护一个数组tails，tails[len]表示长度为len的上升子序列的最小结尾值。遍历原数组时，用二分在tails里找到第一个大于等于当前元素的位置，替换它。这个技巧学起来简单，但你要是不提前了解，很难在考场上自己想到。

另一个常见优化是用树状数组或线段树加速转移。比如二维DP里面有一个max操作，而且转移来源是一段连续区间的最值，那就可以用数据结构维护区间最值，把O(n)的转移降到O(log n)。这种优化在竞赛里尤其常见，面试里一般考察得少，但属于“知道有这个东西”能加分的范畴。

5.4 斜率优化与四边形不等式：慎入

这两个优化是竞赛向的内容，但既然聊到优化套路，我还是把名字报出来。斜率优化用于转移方程里出现i和j的乘积项，比如dp[i] = min(dp[j] + a[i]*b[j])，这时候可以用单调队列维护一个凸包，把复杂度降一维。四边形不等式用于区间DP里状态转移具有单调性的情况，可以优化掉一维枚举。

我不是劝所有人都去学这两个东西。如果你只准备面试，完全没必要碰；如果打竞赛，等前面那些基础优化都熟练了再学也不迟。我当年花了整整一周才把斜率优化啃明白，说实话性价比不高，除非你的目标赛事真的会出这类题。

6. 新手最常见的6个DP错误与调试心法

6.1 六大致命错误速查

我这些年帮人改过的DP代码，90%都栽在下面这六个问题上：

第一个，数组越界。循环里没处理好边界条件，访问了dp[-1]或dp[n]的位置。Python里dp[-1]不会立刻报错，它会默默取最后一个元素，这种错误特别阴险，不打印中间结果根本发现不了。

第二个，初始化错误。最常见的是把dp所有值初始化为0，但题目需要求最小值，正确的初始值应该是正无穷大。你初始化错了，算出来的最大值永远是0而不是真实答案。

第三个，遍历顺序错误。该倒序的时候正序，该按长度从小到大却按位置顺序。这个问题在背包和区间DP里最频发。

第四个，状态定义含糊。用一个维度描述了两件事，导致转移时无法判断当前状态到底属于哪种情况。这种错误不会崩溃，只会让你的答案莫名其妙地偏小或偏大。

第五个，溢出问题。C++选手的低级失误。DP数组开int，中间计算却可能超过2^31，必须改用long long。Python虽然不用考虑这个，但如果你做的是C++算法题，这是实打实的坑。

第六个，忽略边界特判。比如数组长度为0、n等于1这种边界情况，经常导致dp数组太小，循环直接越界。

6.2 调试DP的方法论：打印、对拍、手推

DP出错了怎么排查？我有一套固定的流程，你照着来基本能秒杀90%的问题。

第一步，打印整张dp表。把每个状态的最终值都打出来，拿一个特别小的样例，人肉对照手推的结果。这一步能发现绝大多数“状态转移逻辑错误”。我最常做的事就是print(dp)，然后盯着表格看三分钟，立刻就能定位到第一个开始不对的位置，再顺着那个位置往前推，问题就出来了。

第二步，如果是逻辑实在对不上，回到状态定义重新审视，别在转移方程上硬调。很多人喜欢拿着一个方程反复试不同的初始值，越试越乱。正确的做法是回到五步法的第一步，先问自己：dp[i][j]到底代表什么意思，这个定义能覆盖所有可能的情况吗？

第三步，对拍。拿你的DP版本和一个暴力搜索版本一起跑随机小数据，比较结果。暴力算法不用管效率，只要正确就行，数据范围控制在n <= 10，跑几百组随机用例，能帮你验证绝大多数的边界情况。我在竞赛里基本人手一套对拍器，没有它我很多DP题根本不敢交。

6.3 用三个问题给DP做“术后复盘”

最后分享一个我每次刷完一道DP题都会问自己的复盘模板，就三个问题：

第一，这道题的状态定义能不能换一种？两种定义优劣在哪？这个问题能帮你拓宽“设计状态”的视野。

第二，转移方程如果漏掉某一条路径，会怎样？这个思考能帮你检查状态覆盖的完备性。

第三，这个题的模型还能套到哪些变体上？比如01背包能套在“选或不选”的决策问题上，LIS能套在“求最长递增序列”的各种变体上。总结模型比刷题数量更重要。

6.4 日常训练安排建议

很多人学DP脑子里没节奏感，今天看背包，明天看数位，后天又回头做LIS，知识碎片化严重。我建议按专题刷，一个专题至少刷到稳定AC 15到20题再换，每个专题刷完必须亲手整理一页自己的“状态定义笔记”。刷完一个专题，得能画出这个专题所有变体的关系图才算过关。

我个人在实际操作中的体会是：DP是最讲究“时机”的算法，你状态定义得好，转移方程几乎是“倒出来”的；定义得不好，后面用再多的优化技巧都像在救一个方向错误的项目。与其急于优化、急于背模板，不如先把每个经典模型的“状态定义为什么这么设计”想透彻。等你刷到一定量之后，你会突然发现，DP题其实就那几种套路，换汤不换药，那一刻你就真的入门了。