AI面试算法题之动态规划通关指南

可视化演示

DP核心思想

登山者出发前，手里有两样东西：一张标满营地位置的地图，一本空白的小本子。他深知，翻越整座山的最好办法，是先征服脚下的一座座小山坡——每个小山坡怎么走，都不会被后面的大山影响；整座山的最优路线，就是由这些小山坡的最优路线拼接出来的。这是他智慧的起点：大问题的最优解，藏在子问题的最优解里。

计算科学家把这种智慧叫作动态规划（Dynamic Programming，DP）。它解决的是两类问题。第一类叫最优子结构：原问题的最优解可以通过子问题的最优解推导出来，就像整条登山路线由一段段最优山道拼成。第二类叫重叠子问题：同一个子问题会被反复用到，就像从不同路线出发的人都会经过同一个营地。如果不用 DP 而用裸递归，同一段山路会被重复走无数遍；DP 的做法是：每个营地只算一次，把答案记在小本子上，下次直接查。

实现 DP 有两条路。自顶向下叫记忆化搜索：按递归思路计算，但把算过的结果缓存起来。自底向上叫递推：从第一个子问题开始，按顺序一个个算到目标，面试中更常用。斐波那契数列是理解这两个概念的经典例子，设 f(n) 为登上第 n 级台阶的方案数：

回到登山者身上。他每征服一个小山坡，就在本子上写下“这个营地的营地最优值”；后面来的登山者看到记录，就不用再自己探一遍路。斐波那契的 f(n) 和登山营地记录本质上是同一件事：把已解决过的子问题答案存下来，避免重复计算。这就是 DP 的全部秘密——它并不神奇，只是比不懂记录的登山者多了一个“小本子”。

状态定义方法

登山者规划路线时，第一件事不是迈腿，而是选营地：在哪些位置扎营、每个营地记录什么信息。营地选得准，后面的路就顺；营地选得偏，整条路线都会绕远。

在 DP 里，“选营地”就是状态定义——决定 dp 数组的下标表示什么、数组里存什么。状态定义是解题中最重要也最容易卡住新手的一步。一个实用技巧是：从题目问什么出发。题目问“前 n 个物品能装下多大价值”，就把 dp[i] 定义为“前 i 个物品的最优价值”；题目问“走到第 i 格的最短步数”，就把 dp[i] 定义为“到达第 i 格的最短步数”。下标 i 就是子问题的“规模刻度”，数组值就是该刻度的答案。这叫作题意抽象。

状态定义还要注意两点。一是维度：只和“位置”有关的问题用一维 dp[i]；和“位置 + 剩余容量”两个因素有关的问题用二维 dp[i][j]；因素再多就继续加维度。二是无后效性：一个状态一旦确定，它后面的决策不需要知道“当初是怎么到这个状态的”，就像登山者到了某个营地后，只需关心从这里到山顶怎么走，而不必关心自己之前走过哪条路。如果状态定义把“来时的路线”都记进去，维度会爆炸，递推也无法进行。

营地的位置定了，本子上每一行写什么也就定了。很多同学写不出转移方程，其实是状态定义太模糊——就像登山者连营地都没选好，当然不知道下一段路怎么走。状态定义是 DP 的地图，画好地图，铺路才有方向。

状态转移方程

营地选好之后，登山者开始铺路。他从大本营出发，每到一个新营地都会问自己：我是从上一个营地直接走过来的，还是绕过了上一个营地、从更早的营地过来的？每段山路都有一个“路标”，写着这条路线的收益。

在 DP 里，铺路对应的就是状态转移方程——回答“dp[i] 是从哪个状态、经过什么决策得到的”。写转移方程有两个思路：一是看谁来，想清楚从哪个子问题转移来；二是看决策，每个状态有哪些选择，选最优。这就是决策枚举的过程。比如经典的“打家劫舍”：一排房屋，每间有金额 nums[i]，不能偷相邻两家。站在第 i 家门前只有两个选择——不偷它，答案就是前 i-1 家的最优解 dp[i-1]；偷它，就必须跳过第 i-1 家，答案是 dp[i-2] + nums[i]。两个选择取最大，就是当前营地的递推关系。

写转移方程时最容易犯错的是边界衔接——比如 i=1 时，dp[i-2] = dp[-1] 会越界，这时要么先手动初始化 dp[0]、dp[1]，要么在循环里加特判。把状态比作营地名单，转移方程就是连接营地的山路网，每一段路的“路标”都写着：从哪个营地出发、经过什么决策、收益是多少。转移方程写得顺，登山者就能一路小跑；写得乱，每一步都卡在半山腰。

初始化与遍历

登山者对路线的第一步永远是定大本营：起点在哪里、第一段路怎么走。大本营没搭好，后面所有营地都失去了参照——这就是 DP 里的初始化。

初始化给递推提供地基边界。以打家劫舍为例，dp[0] 表示只有第一间房时的最优值，显然就是 v_1；dp[1] 表示有两间房且不能同时偷，答案是 max(v_1, v_2)。这两个值一旦定好，从 i=2 开始循环，转移方程就有东西可用了。

除了初始值，还要注意数组大小和遍历顺序。数组长度要能容纳所有状态下标，防止越界；有些题目为了统一逻辑，会加一个“哨兵”（dummy 节点），在 dp 数组前多开一位，让 dp[0]、dp[1] 对应真实的第一、二个元素，把特判吸收进初始化。遍历方向则要服从依赖关系：计算当前状态需要哪些更小的状态，就保证那些状态先被算出来。登山者从不多想，他记得最牢的一句话就是：地基决定高度，方向决定终点。 初始化把大本营钉牢，遍历顺序保证每一步都踩在已经铺好的山上。

背包问题

登山行囊的空间是有限的。出发前，他对着地图和物品清单纠结：每一件补给品都有重量和价值，行囊最多能装容量 C 的东西，怎么塞才能让总价值最大？这正是背包问题的考法。

0-1 背包是最基础的一类：每件物品只能选一次。设 dp[j] 表示容量为 j 的行囊能装下的最大价值。遍历每件物品 i 时，对容量 j 只有两个选择：不装它（保持 dp[j]），或腾出 w_i 的空间装下它（dp[j - w_i] + v_i）。

如果每件物品可以无限次取用，那就是完全背包——这时内层循环反而要从小到大正序遍历，让“取一件再取一件”成为可能。两类背包只差一个遍历方向，却是面试官最爱埋的坑。此外，二维 dp[i][j] 可以优化成一维 dp[j]，这种空间优化思想在编程界有个朴素的称呼——滚动数组：不需要保留全部历史，只滚动保留当前有用的几行。登山者最后把行囊塞得满满当当，既没超重，价值又最高。他总结道：背包问题的本质，是在容量限制下做“要还是不要”的取舍；一维数组加倒序遍历，就是这场取舍中防止贪婪重复的金钥匙。

打家劫舍

有一片营地建在环形山道上，首尾相接。保安每隔一个营地设一个岗哨，登山者不能连续走进两个相邻营地，否则会惊动岗哨。面对一圈价值不同的营地，怎么走才能拿到最大收益？这就是打家劫舍的环形版本。

先看线性序列。一排营地从 0 到 n-1，状态转移和第三节一样：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。物理含义很直观：走到第 i 个营地，要么不进去（沿用 dp[i-1]），要么进去（跳过第 i-1 个营地，拿 nums[i] 并加上 dp[i-2]）。

更妙的是状态压缩：线性打家劫舍的递推只用到 dp[i-1] 和 dp[i-2]，所以根本不需要存整个数组，用两个变量滚动更新即可，空间复杂度从 O(n) 降到 O(1)。面试中主动说出这一步，往往能让面试官眼前一亮。登山者面对环形山道没有慌，他只是把环上某一段路“剪开”，变成自己熟悉的直线，然后把两条可能的直线都走一遍，取更好的那条。遇到环形、圆形这类首尾相连的问题，先想想怎么把它剪成直线——这是打家劫舍与许多变形题通用的破局思路。

解题模板

经验丰富的登山者每次出发前都检查四件装备：地图（状态定义）、路标（转移方程）、大本营（初始化）、登山杖（遍历顺序）。这四件装备齐全，再陡的山也不怕。面试中遇到 DP 题，同样按四步走。

四步模板如下。第一步，定状态：明确 dp 数组的下标和值分别表示什么。第二步，写转移：站在当前状态问自己“从哪个状态、经过什么决策能到这里”，写出递推关系。第三步，初始化：把地基边界填好，常需要特殊处理 dp[0]、dp[1] 或空集情况。第四步，定遍历顺序：确保当前状态依赖的子状态已经计算完毕，根据依赖方向选择正序或倒序。

面试时还有一个小技巧：先说思路再写代码。比如开口就说“这道题我用一维 dp，dp[i] 表示前 i 家的最大收益，转移是 max 两个分支，复杂度 O(n)”，然后才动笔。老登山者把四件装备挂在山杖上，一步一步稳稳走向山顶。他明白，登山不是拼速度，而是拼章法；面试 DP 题不是拼灵感，而是拼模板。 四步走顺畅了，任何 DP 题在你眼里都只是“换了一张地图的登山路线”。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-def house_robber(nums):    if not nums:        return 0    n = len(nums)    if n == 1:        return nums[0]    dp = [0] * n    dp[0] = nums[0]    dp[1] = max(nums[0], nums[1])    for i in range(2, n):        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])    return dp[n - 1]  def house_robber_circle(nums):    if len(nums) == 1:        return nums[0]    return max(house_robber(nums[:-1]), house_robber(nums[1:]))  def knapsack_01(weights, values, capacity):    dp = [0] * (capacity + 1)    for w, v in zip(weights, values):        for j in range(capacity, w - 1, -1):            dp[j] = max(dp[j], dp[j - w] + v)    return dp[capacity]  if __name__ == '__main__':    nums = [2, 7, 9, 3, 1]    print('linear rob:', house_robber(nums))    print('circle rob:', house_robber_circle(nums))    weights = [2, 3, 4, 5]    values = [3, 4, 5, 6]    print('knapsack:', knapsack_01(weights, values, 8))

1. dp = [0] * n先铺好 n 个营地的“小本子”，每个位置初始为 0 分。
2. dp[0] = nums[0]初始化第一个营地：只有一间房时直接拿它的金额。
3. dp[1] = max(nums[0], nums[1])初始化第二间房：相邻不能都偷，选金额更大的那家。
4. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])状态转移方程：不偷当前 vs 隔一家偷当前。
5. max(house_robber(nums[:-1]), house_robber(nums[1:]))环形拆线：分别求“不偷尾”和“不偷头”的线性最优再取最大。
6. dp = [0] * (capacity + 1)一维背包数组，下标 j 就是行囊容量。
7. for j in range(capacity, w - 1, -1):倒序遍历容量，防止同一件物品被重复装入。
8. dp[j] = max(dp[j], dp[j - w] + v)背包核心转移：不装当前物品 vs 腾出空间装下它。

常见误区

面试题