企业官网建设流程全解析

1. 动态规划为什么是面试“钉子户”

如果你刷过一阵子算法题，会发现动态规划几乎出现在每一场像样的技术面试里。不管是校招还是社招，面试官总喜欢拿一道DP题来试探候选人的思维深度——不是看你背了多少题，而是看你能不能把一个大问题拆成小问题，能不能从小问题的答案一步步推出大问题的答案。这个思维过程，恰恰是日常工程里解决复杂问题最需要的能力。

我面试别人时有个习惯：先让候选人做一道中等难度的DP题。如果他能把状态定义讲清楚、把转移方程推导出来，哪怕最后代码没写完，我也会给不错的评价。因为DP题的核心不在于代码量，而在于建模能力。反过来，如果候选人上来就背着模板套题，一旦题目变形就卡住，那基本可以确定他的算法功底是浮的。

这篇文章我打算系统梳理经典动态规划里最高频的几类题型，包括它们的状态设计思路、转移方程推导过程、初始化细节、遍历顺序的讲究，以及我在实际刷题和面试中踩过的坑。内容面向正准备面试的读者，也适合学完基础DP但想加深理解的人。全篇围绕一个目标：让你遇到一道新DP题时，能有一套清晰可复用的思考路径，而不是靠运气蒙。

2. 先建立DP的正确认知：状态、转移、初始化、遍历顺序

2.1 DP的本质：用子问题的答案组合出原问题的答案

很多初学者一上来就背“最优子结构”“无后效性”这些术语，背得滚瓜烂熟，做题还是一脸懵。我更喜欢用一个生活化的类比来解释。

假设你想知道从一楼爬到十楼一共有多少种走法，每次可以走一级或两级台阶。这个问题如果你从十楼往下看，会发现：到达十楼的最后一步，要么是从九楼跨一级上来，要么是从八楼跨两级上来。那么到达十楼的总走法，就等于到达九楼的走法加上到达八楼的走法。这就是最典型的DP思路——不直接去枚举所有路径，而是先去解决更小的子问题，然后用子问题的答案组合出大问题的答案。

这个过程有两个关键点。第一，子问题之间是重叠的，同一个子问题会被反复用到，所以需要把计算结果存下来，避免重复计算。第二，每个子问题只关心自己的答案，不关心它是怎么得到的，这就是“无后效性”的通俗解释——过去的具体路径不影响未来的决策。

你在面试中讲DP题时，如果能用这种直白的语言把本质讲清楚，面试官通常会挺认可。因为这说明你不是在背题，而是真的理解了DP之所以高效的原因——用空间换时间，把指数级枚举降成多项式级计算。

2.2 一个DP题的标准构成：四个要素缺一不可

我习惯把每一道DP题都拆成四个要素来审视：

• 状态定义：dp数组的每个元素代表什么含义
• 转移方程：当前状态如何由之前的状态推导出来
• 初始化：边界状态是什么，dp数组的起点值怎么设定
• 遍历顺序：按什么顺序填表，才能保证推导某个状态时，它依赖的状态已经算好了

这四个要素里，状态定义是灵魂，也是最难的一步。同一个题目，状态定义得好，转移方程可能只写一行；定义得不好，可能要写好几行，甚至根本推不出来。比如经典的LIS问题（最长递增子序列），有人定义dp[i]为“以第i个元素结尾的最长递增子序列长度”，转移就非常自然：遍历i之前的所有j，如果nums[j] < nums[i]，就用dp[j] + 1来更新dp[i]。这个定义把焦点放在“结尾元素”上，就能自然地利用子问题的性质。

而初始化则是很多人容易忽略的地方，但它直接决定正确性。比如斐波那契数列的dp[0]和dp[1]如果没设置对，后面全是错的。再比如背包问题里，dp[0]表示容量为0时能装的最大价值，这个边界必须为0，否则后续推导就不成立。

遍历顺序也很有讲究。二维DP里，外层循环遍历物品还是遍历容量，结果可能完全不同；一维滚动数组里，遍历容量必须倒序，否则同一个物品会被重复使用——这是01背包问题里最容易出错的地方，后面我会专门展开讲。

2.3 DP和递归、贪心的分界线在哪里

面试中经常被追问的一个问题是：“这道题你为什么不递归做？为什么不用贪心？”你需要能清晰地划出分界线。

递归和DP的关系其实很近：递归是自顶向下，DP是自底向上。递归写起来直观，但如果没有记忆化，复杂度是指数级的；有了记忆化，本质上就是DP的另一种写法。所以有些题目你用递归加缓存也能过，但面试时我更推荐用迭代的DP写法，因为它空间占用更容易控制，也面试官也更容易看清你的思路。

贪心和DP的区别更微妙。贪心每一步都做当前看起来最优的选择，不考虑未来；DP则考虑所有可能的选择，并从中取最优。判断标准很简单：如果局部最优能推出全局最优，用贪心；如果不行，就用DP。比如找零钱问题，如果硬币面额是1、5、11，要找15元，贪心会先拿11再拿4个1，得到5枚硬币；但最优解是3枚5元硬币——这种情况下贪心失效，必须用DP枚举所有组合。把这个例子讲给面试官听，比干背定义有说服力得多。

3. 面试常考的三类经典DP模型拆解

3.1 爬楼梯与斐波那契：最简单的入门模型

爬楼梯问题（LeetCode 70）是DP入门的必修题，也是高频面试题。题目描述很简单：每次可以爬1级或2级台阶，爬到楼顶有多少种不同的方法？

状态定义非常直接：dp[i]表示爬到第i级台阶的方法数。转移方程就是dp[i] = dp[i-1] + dp[i-2]，因为到达第i级台阶，只能从第i-1级跨一步，或者从第i-2级跨两步。初始化dp[0] = 1（原地不动算一种方法），dp[1] = 1。

这个题虽然简单，但面试官往往会做几个变体考察：

• 如果每次可以爬1、2、3级呢？转移方程变成dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
• 如果相邻两步不能走相同的步数呢？这就得把状态扩展成二维：dp[i][j]表示到达第i级台阶，最后一步走了j级的方法数。
• 如果不只是问方法数，而是要求输出所有走法呢？那就得用回溯了，因为DP只适合求“计数”或“最值”，不适合穷举所有具体方案。

注意，这个题的数值会增长得很快，所以通常要对结果取模（比如10^9+7）。很多候选人在这里翻车，不是因为思路不对，而是忘了取模导致溢出。我在面试中见过好几个人在最后一步栽在这个细节上，十分可惜。

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

3.2 01背包问题：面试翻车重灾区

01背包是动态规划里最经典的模型，也是面试中的“分水岭”题目。题目描述：有N件物品和一个容量为V的背包，每件物品只能用一次，第i件物品的重量是w[i]，价值是v[i]，求背包能装下的最大价值。

二维状态定义：dp[i][j]表示前i件物品中选取若干件，放入容量为j的背包时能获得的最大价值。对于第i件物品，只有两种选择：不装，则dp[i][j] = dp[i-1][j]；装，则dp[i][j] = dp[i-1][j-w[i]] + v[i]（前提是j >= w[i]）。所以转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。

这个问题的核心难点在于空间优化。观察转移方程可以发现，第i行的状态只依赖第i-1行，所以可以用一维数组滚动更新：dp[j] = max(dp[j], dp[j-w[i]] + v[i])。但这里有个极其关键的细节——内层循环必须从大到小遍历容量。

为什么？因为dp[j-w[i]]在正序遍历时已经被当前物品更新过了，用的是当前物品装了一次的结果，这会导致同一件物品被重复选取，变成了完全背包。而倒序遍历时，dp[j-w[i]]还是上一次外层循环留下的旧值，也就是还没有考虑当前物品的状态，这样就保证了每件物品只用一次。这个细节我在面试中问了不下二十次，能正确答出原因的候选人不到一半。

def zeroOnePack(N: int, V: int, w: list, v: list) -> int: dp = [0] * (V + 1) for i in range(N): for j in range(V, w[i] - 1, -1): # 关键：倒序遍历 dp[j] = max(dp[j], dp[j - w[i]] + v[i]) return dp[V]

背包问题的变体非常多：完全背包、多重背包、分组背包、二维费用背包，每种都是在基础模型上做一些改动。面试时要能快速识别题目属于哪种模型，然后对应调整状态定义和遍历顺序。比如完全背包每件物品可以无限次使用，遍历顺序就变成正序；分组背包每组只能选一件，就要加一层循环处理组内选择。这些变体不要求你全部背下来，但至少要知道核心的思考方式。

3.3 最长递增子序列与最长公共子序列：序列型DP的代表

序列型DP是面试另一大热门，其中LIS（最长递增子序列）和LCS（最长公共子序列）是两道必刷题。

LIS问题（LeetCode 300）：给定一个数组，求最长严格递增子序列的长度。状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度。初始时每个元素自身构成一个长度为1的子序列，所以dp[i] = 1。转移时，遍历i之前的所有j，如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)。最后答案是所有dp[i]中的最大值，而不是dp[n-1]——我见过好几个候选人栽在这里，因为他们习惯性认为最后一项就是答案。

def lengthOfLIS(nums: list) -> int: 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) if n > 0 else 0

这里再补充一个进阶版：维护一个tails数组，用贪心加二分把时间复杂度从O(n^2)降到O(nlogn)。tails[k]表示长度为k+1的递增子序列的最小结尾元素。遍历数组时，用二分查找找到第一个大于等于当前元素的位置并更新它。这个技巧面试时属于加分项，但我建议先把基本版本写对，再考虑优化。

LCS问题（LeetCode 1143）：给定两个字符串text1和text2，求它们的最长公共子序列长度。状态定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。

转移方程分两种情况：

• 如果text1[i-1] == text2[j-1]，说明当前字符相等，dp[i][j] = dp[i-1][j-1] + 1
• 如果不等，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

边界条件：dp[0][j]和dp[i][0]都为0，因为空字符串和任何字符串的公共子序列都是空。

思考LCS问题时，代入感很重要。你可以想象成两个人各拿一个字符串，从左往右扫描，逐个字符比较。相等就都往前走一步并计数加一；不相等就分别试一下“跳过text1的字符”和“跳过text2的字符”两种情况，取较大的结果。这种从实际过程出发想问题的方式，比死记转移方程有用得多。

def longestCommonSubsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]

顺带提一句，编辑距离（LeetCode 72）是LCS思路的进阶版，也是极高频面试题。它定义了三种操作：插入、删除、替换，求把一个字符串变成另一个字符串的最少操作次数。状态定义dp[i][j]表示word1的前i个字符变成word2的前j个字符需要的最少操作次数。重点理解三种操作对应转移方程里的哪一项——删除字符对应dp[i-1][j] + 1，插入字符对应dp[i][j-1] + 1，替换字符对应dp[i-1][j-1] + 1。这个题啃下来，你对DP的理解会再上一个台阶。

3.4 数字三角形：理解“从底向上递归”的最佳样例

数字三角形是一道很好的思维进阶题。题目通常描述为：给定一个三角形，从顶部到底部寻找一条路径，使得路径上的数字之和最大，每一步只能移动到下一行中相邻的数字上。

这道题的常见做法有两种：自顶向下和自底向上。自顶向下的话，状态定义dp[i][j]表示从顶部走到第i行第j个位置的最大路径和，转移方程为dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]，需要注意边界位置只有一条路径可选。自底向上的做法更简洁：从最后一行开始往上推，dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])，最后答案就是dp[0][0]。

实际做题时我更喜欢自底向上，因为它不需要处理边界条件，代码更优美。比如在LeetCode上，数字三角形有很多变种，从“最小路径和”到“最大路径和”，思路完全一样。如果你把这道题理解了，再看矩阵路径问题（比如机器人从左上角走到右下角的路径数或最小代价），会发现其实就是把三角形换成了矩阵，思路完全一脉相承。

面试中的一个常见追问是：“如果让你输出具体路径，怎么改？”这时候就要在DP的基础上额外维护一个路径数组，在每个状态转移时记录下选择的方向，最后从终点倒推回起点。这个思路很重要，因为很多面试官喜欢从“求最优值”升级到“求最优方案”。

4. 一套可复用的DP解题流程

4.1 从识别题目到写出代码的五个步骤

我在刷题时总结了一套固定的流程，现在分享出来。这套流程让我在面试中遇到新题时不会慌乱，也推荐你试试。

第一步，识别题型。拿到题目先判断它是不是DP题。常见的信号包括：求最值（最大、最小）、求方案数、求可行性（能不能达到目标）、数据规模在10^5以内但暴力枚举会爆炸。这些特征一出现，优先往DP方向想。

第二步，设计状态。这是最关键的一步。问自己几个问题：问题的“子问题”是什么？子问题需要哪些参数来描述？一维dp够不够？还是需要二维？甚至三维？一般来说，状态定义得越贴近“原问题的规模缩小的版本”，就越容易推导转移方程。

第三步，推导转移方程。这一步的核心是“站在当前状态，思考最后的动作是什么”。比如爬楼梯问题，到第i级台阶的最后一步是跨1级还是2级；背包问题，第i件物品装还是不装；LCS问题，当前两个字符相等还是不相等。把这个“最后一步”想清楚，转移方程就写出来了。

第四步，确定初始化。回到状态定义，思考“最小的子问题”是什么，边界条件怎么设。这一步最容易出错，但也是最好检查的——用题目给的例子手动模拟几轮，如果边界不对，很快就会暴露。

第五步，确定遍历顺序并写代码。根据状态转移方程看依赖关系：如果dp[i]依赖dp[i-1]，从前往后遍历；如果依赖dp[i+1]，从后往前遍历；二维状态看行和列的依赖方向。遍历顺序从数学上讲是“拓扑序”，简单理解就是保证算当前状态时，它依赖的所有状态都已经算过。

4.2 用一个完整例子走一遍流程

以LeetCode 322零钱兑换为例，走一遍我们这个流程。题目：给定不同面额的硬币coins和一个总金额amount，求凑成总金额所需的最少的硬币个数，若无法凑成则返回-1。

第一步，识别题型：求最少硬币个数，是求最值问题，符合DP特征。

第二步，设计状态：dp[i]表示凑成金额i所需的最少硬币数量。这个状态定义很自然，因为“凑成更小的金额”就是“凑成总金额”的子问题。

第三步，推导转移方程：要凑成金额i，最后一步一定是放了一枚面额为coin的硬币，所以dp[i] = min(dp[i - coin] + 1) for coin in coins and coin <= i。注意这里枚举所有硬币，这是完全背包的思想——每种硬币可以用无限次。

第四步，初始化：dp[0] = 0，表示凑0元不需要任何硬币。其他dp[i]初始化为一个很大的数（比如amount + 1），表示暂时不可达。为什么要用这么大的数？因为目标是求最小值，用一个大数作为“无限大”占位，方便后续被更新。

第五步，遍历顺序和代码：dp[i]依赖dp[i-coin]，coin是正数，所以i从小到大遍历是安全的。

def coinChange(coins: list, amount: int) -> int: dp = [amount + 1] * (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] <= amount else -1

我们把这几道经典题放在一起对比一下，面试前快速扫一眼会有帮助：

4.3 空间优化的通用套路

很多DP题在写出二维状态后，面试官都会追问一句：“能不能优化空间？”这是因为空间优化能体现你对状态转移本质的理解。

最常用的优化手段是滚动数组。比如LCS的dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]这三项，本质上只涉及上一行和当前行，所以可以用两行滚动，空间从O(mn)降为O(n)。如果能再进一步，观察到dp[i][j-1]就是当前行前一个格子，那连第二行都能省掉，只用一维数组加一个临时变量保存左上角的值。

不过我要提醒一下，空间优化往往会让代码变得抽象，面试现场如果写不出来，老老实实用二维数组也完全没问题。关键是先把功能做对，再谈优化。我见过太多候选人强行优化，结果在“左上角值被覆盖”这种细节上翻车，反而得不偿失。

另一个常见的空间优化场景是数位型DP，这类题时常用到前缀和技巧。比如子数组和等于K的个数、最大子数组和等问题，都用到类似“前缀和+哈希表”的优化思路。本质上还是DP，只是把状态存到哈希表里，换取更快的查找速度。这块可以作为进阶内容补充学习，但不是这篇文章的重点。

5. 实操过程中我踩过的坑和排查经验

5.1 状态定义错了，后面全白搭

我刚开始刷DP题时，踩过最深的一个坑就是状态定义不够“完整”。举一个具体例子，LeetCode 152乘积最大子数组。我最开始的状态定义是dp[i]表示以第i个元素结尾的最大子数组乘积。这个定义看起来合理，但遇到负数就出问题了——因为当前的最大乘积可能是由之前的最小乘积乘上当前负数得到的。

正确的做法是同时维护两个状态：dpMax[i]表示以第i个元素结尾的最大乘积，dpMin[i]表示以第i个元素结尾的最小乘积。这样当遇到负数时，通过交换最大和最小就能正确处理。这个经历让我深刻体会到：状态定义不能只顺着题目的表面意思走，要想清楚数据之间的相互作用。

排查这类问题有个实用技巧：当你发现转移方程对某几个测试用例始终不对时，不要急着改方程，先回头检查状态定义是否覆盖了所有情况。如果状态变量不足以区分不同的子问题形态，那无论怎么调转移方程都是徒劳。

5.2 遍历顺序错了，结果悄悄变错

在讲解01背包空间优化时，我强调了内层循环必须倒序遍历。这个问题的本质在于“状态依赖的时效性”：一维滚动数组当前格子的值，可能来自上一轮（旧值），也可能来自这一轮（已被当前物品更新）。倒序遍历保证了在用到dp[j-w[i]]时，它还是上一轮的旧值，从而保证每件物品只被用一次。

类似的坑在完全背包里也存在，只不过方向相反——完全背包需要正序遍历，因为允许同一种物品多次取用。我记得有一次刷一道完全背包的变体题，因为没仔细审题，把正序写成了倒序，结果提交后有两三个用例怎么都过不了。用调试器一看才发现问题，当时就意识到遍历顺序绝不是可以随手一写的细节。

排查遍历顺序问题的最好方法是打表观察。把dp数组在每一轮循环后的值打出来，对照手算的期望值，通常一眼就能看出是哪里的更新顺序出了问题。DP题的调试比普通题更依赖纸笔推演，别偷懒。

5.3 初始化值选不对，答案差之千里

初始化是DP里最容易被忽视、却最容易造成Bug的环节。最常见的类型是“极大值/极小值”的选取。比如零钱兑换问题，如果你把dp[i]初始化成float('inf')，后面做min运算就没问题；但如果初始化成0，那min的结果永远是0，整个DP就是废的。

另一种情况是边界条件的上下界。比如LCS中dp数组的维度是(m+1) x (n+1)，多出的第0行第0列就是用来表示空字符串的情况。如果你把数组开成m x n，那就没有空字符串的边界状态，初始化就会无从下手，后续越界也是必然。

我建议在写完代码后，先用题目给的示例逐行模拟一遍。这个过程虽然耗时，但对发现边界问题极其有效。特别是当dp数组下标从1开始时，循环里的i-1、j-1这样的偏移最容易出错，手动推两轮就能查出来。

5.4 判断错误：这题到底能不能用DP

面试中还有一种容易丢分的场景：题目其实不适合用DP，但你硬套DP框架。比如求全排列的所有具体方案，这是典型的回溯/搜索问题，DP只适合求方案数，不适合枚举方案。再比如求最短路径，如果图中存在负权边，Dijkstra和传统的DP方法都需要调整。

判断一个题能不能用DP，核心看两条：第一，问题有没有最优子结构——即大问题的最优解能否由子问题的最优解推导出来；第二，子问题之间有没有重叠——如果子问题完全不重叠，用递归就行了，DP没有收益。如果你能快速说出这道题满足这两条，再用DP做，基本不会出现原则性错误。

5.5 面试时写DP题的讲解顺序

最后分享一个面试技巧。写DP题时，不要闷头就敲代码，而要边写边讲。我通常按这个顺序讲：先讲状态定义是什么，为什么这样定义；再讲转移方程怎么来的，重点说“最后一步的选择”是什么；然后讲初始化为什么这么设；最后提一下遍历顺序和空间复杂度。这样讲下来，面试官能清楚地看到你的思路过程，即使最后代码有小Bug，也能通过沟通弥补。

如果中途发现自己状态定义推不下去了，千万别慌。直接跟面试官说：“我换一个状态定义再试试。”这比死磕到底要加分得多。面试官更看重你从错误中调整思路的能力。这类情况我在实际面试中遇到过好几次，有一次候选人把状态从一维改成二维后，思路瞬间通了，最终顺利给出了正确的转移方程，虽然花的时间多一点，但最后评价并不差。

6. 经典DP题的进阶方向，但这几道先吃透

这篇文章我们聚焦在“经典动态规划1”，主要覆盖了入门级的爬楼梯、背包、LIS、LCS和零钱兑换。这些题是DP的地基，一定要吃透。基础打牢后，你可以往几个进阶方向拓展：区间DP（比如戳气球、最长回文子序列）、树形DP（比如打家劫舍III、二叉树的最大路径和）、状压DP（比如旅行商问题）、数位DP等等。这些题型在面试中也经常出现，但通常排在基础题之后考，所以先把当下的内容消化掉更为关键。

我个人的建议是：以这些经典题为抓手，把每一道的状态定义、转移方程、初始化、遍历顺序这四要素烂熟于心，再延伸到变种题上去。刷题时不要贪多，一道题吃透比草草刷十道有用得多。所谓吃透，就是合上答案能独立推导、能随口说出代码的每一行为什么这样写、能回答出面试官的各种追问。

最后，我建议每做完一道题，都在笔记里写一下“这道题的状态设计对我来说是自然的还是不自然的”。如果觉得不自然，说明你对这类问题的感受还不够深，隔几天回来重做一遍。我的很多学生用这个办法，不到一个月就对DP题形成了比较稳定的直觉。这一点对面试备考的帮助，远比刷题数量要大。