每年一到秋招刷题季“动态规划”这四个字都能劝退一大波人。我最近整理老题单把美团点评2017秋招笔试那几道常见动态规划编程题又撸了一遍发现它们特别适合拿来当DP入门教材。别看是好几年前的题大富翁游戏、拼凑钱币这两道题几乎覆盖了面试笔试里最高频的两类DP模型线性递推和背包计数。这篇文章就当一份解题报告来写把从读题、建模、写状态转移方程到边界处理、代码实现、复杂度优化的完整过程全部拆开。适合正在准备秋招、或者动态规划一直没开窍的同学参考也适合想系统梳理DP套路的人拿来当复习清单。1. 先说清楚这道题到底在考什么1.1 两道真题的题面长什么样大富翁游戏这个题在牛客网和网上的各种回忆帖里流传很广题面大致是这样有一个长度为 n 的一维棋盘玩家从第 0 格出发每次投一次骰子骰子点数 1 到 6往前走对应步数问到达第 n 格一共有多少种不同的走法。n 一般给到 100 以内输出方案数。样例的话n3 输出 4因为 3 可以由 111、12、21、3 这四种“走法组合”到达。注意不同回忆版本里棋盘编号可能有细微差别有的从第 1 格开始但本质是同一个问题把目标位置看成下标最后一步来自前 1~6 格。这个题的学名叫“爬楼梯”的扩展版原版爬楼梯一次只能走 1 或 2 步这里扩展成最多 6 步。另一道题是拼凑钱币也叫换零钱或者硬币找零题面大致是给定一个总金额 sum 和 m 种不同面额的硬币每种硬币数量无限问有多少种不同的组合方式可以把 sum 正好凑出来。组合方式不计顺序也就是说 [1,2] 和 [2,1] 必须算同一种。示例是 sum5硬币面额分别为 1、2、5答案是 4四种分别是 11111、1112、122、5。这两道题一道是线性递推一道是背包计数都是动态规划面试笔试里的熟面孔。看懂它们等于把 DP 两大主流分支的门都推开了。这篇文章后面所有的分析都以这两道题为主线。我不光写最终代码更会把“为什么状态这么定义”“为什么边界是 0”“为什么循环顺序不能反”这些容易想当然的地方讲清楚。因为秋招笔记里最不缺的就是“只看懂了答案、换个题就不会”的遗憾缺的是把一类题彻底吃透的扎实劲儿。1.2 为什么秋招笔试偏爱动态规划笔试出题人喜欢 DP首先是因为它考的不是背模板而是把实际问题抽象成“状态 转移”的建模能力。同样的代码量DFS 只要会递归就能写BFS 记住队列套路就能推但 DP 没有一个固定模板可以背——你至少要自己想清楚“dp[i] 代表什么”“从哪些地方转移过来”“边界怎么初始化”。这三个问题想不明白代码根本写不下去所以 DP 题的区分度非常高。其次DP 题很适合设置“小陷阱”。比如大富翁游戏里 dp[0] 到底是 0 还是 1拼凑钱币里内层循环从 coin 开始还是从 1 开始背包循环顺序正着写还是倒着写。这些细节不踩一次坑很难长记性而笔试环境里刚好能快速筛掉“看着会但一写就错”的人。我见过太多人在这些细节上翻车明明思路全对就是差一个符号、一个等号最后整题没分。第三DP 的应用范围是真的广。移动端路径规划要考虑状态转移广告投放的预算分配是背包问题文本编辑器的最少编辑次数是经典二维 DP甚至车辆调度、资源分配这类工程问题也大量用到动态规划思想。企业面试官看到你能流利讲清楚一个 DP 题至少能确认你具备把业务问题抽象成数学模型的潜力。算法类型核心考点难度分布笔试出现率DFS/BFS遍历和状态去重入门高贪心证明能力中等偏高中动态规划状态建模 转移方程中高高所以秋招笔试里 DP 几乎是必考题型美团点评这套题也不例外。当然相比 LeetCode 上一些动不动就上树形 DP、状压 DP 的难题这套题的难度其实非常友好恰好适合拿来当 DP 的练级起点。2. 看懂DP题的三层递进思路2.1 从暴力递归到记忆化搜索再到递推很多同学一看到 DP 题就急着找“状态转移方程”其实这不是最快的路径。我自己的经验是先从暴力递归开始想再逐步优化最后自然落到递推。以刚才的大富翁游戏为例你可以直接定义一个函数 f(i)表示到达第 i 格的方案数。那么站在第 i 格往前看最后一步可能是从 i-1 走 1 步过来也可能从 i-2 走 2 步过来一直到从 i-6 走 6 步过来。于是递归式就出来了# 纯递归f(n)表示到达第n格的方法数 def f(n): if n 0: return 1 if n 0: return 0 total 0 for step in range(1, 7): total f(n - step) return total这个写法逻辑完全正确但效率惨不忍睹。n30 的时候函数会疯狂重复计算同一个子问题比如 f(15) 可能被计算了几百次复杂度接近指数级。笔试里 n 给到 100 就彻底跑不动了。解决办法是加一个缓存把算过的结果存起来也就是记忆化搜索memo {} def f(n): if n 0: return 1 if n 0: return 0 if n in memo: return memo[n] total 0 for step in range(1, 7): total f(n - step) memo[n] total return total记忆化之后每个 f(i) 最多算一次时间复杂度变成 O(n)已经能通过绝大多数题目了。但更工程、更推荐的做法是直接写成自底向上的递推dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): for step in range(1, 7): if i - step 0: dp[i] dp[i - step]为什么笔试里我强烈推荐递推一是迭代不会爆栈递归深度一大有些 OJ 直接栈溢出二是复杂度可以精确预估不会出现“看起来快了但实际没快”的情况三是调试方便把 dp 数组打印出来一眼就能看出哪一步算错了。递归适合在你想不明白递推关系的时候先用它验算记忆化是个保底方案递推才是最终要拿出来的解法。2.2 状态定义是DP的灵魂一个小例子讲透状态定义为什么是灵魂有个生活化类比你想知道从家到公司有多少种走法你不需要每走一步就重新规划路线只需要记住“到达某个路口的方法数”后面所有计算都建立在已经知道的方法数之上。dp[i] 就是那张“路口记录表”。表的每一格写的是什么直接决定了后面怎么算。状态定义含糊导致的后果很典型转移方程写不出来写出来只能过样例换一个数据范围就崩。我见过不少同学对着题目发呆就是因为连“dp[i] 到底代表什么”都没想清楚。好的状态定义有一个标准够用且不冗余。还是大富翁这道题你只需要知道到达某一格的方法数那就定义一维数组 dp[i]如果你把状态定义成“dp[i][j] 表示走了 i 步到达第 j 格的方法数”虽然信息更完整但本题根本不需要步数这个维度白白浪费空间还把问题复杂化。状态定义方式表达的信息是否推荐dp[i] 表示到达第 i 格的方案数只关心“在哪一格”够用推荐dp[i][j] 表示走了 i 步到第 j 格的方案数多记录了“步数”本题用不上不推荐dp[i] 表示“从第 i 格出发走到终点的方案数”视角是反的逻辑也能通但容易绕不推荐我给自己定的状态定义三步法是一看数据范围判断维度二问“最后一步有哪些可能”确定转移来源三定“边界状态”的语义把 dp[0] 这种基石想明白。这三步走完代码基本就是把方程翻译成循环而已。3. 大富翁游戏线性递推DP的完整拆解3.1 题目建模与状态转移方程推导大富翁游戏的核心等式特别简洁dp[i] dp[i-1] dp[i-2] dp[i-3] dp[i-4] dp[i-5] dp[i-6]当 i 1 时成立。如果 i-step 小于 0对应项按 0 处理。dp[0] 1因为“从起点出发、一步不走”本身就是一种到达起点的方案它是后续所有状态的基石。为什么转移项是六项而不是五项或者七项因为骰子的点数范围是 1 到 6最后一步只能来自前 1 到前 6 格少一个点就漏了一种来源多一个点就引入了不存在的走法。这里用到的技巧是“从最后一步反推”。这是 DP 最常用的视角站在当前状态往前看把大问题拆成若干子问题。比如 dp[7] dp[6] dp[5] dp[4] dp[3] dp[2] dp[1]含义是先走到 1 到 6 中的某个格子再一次性走完剩下的步数。这些子问题互不重叠且都已经被计算过所以递推关系成立。整个算法时间复杂度是 O(n*6)近似 O(n)空间复杂度 O(n)n 给到 100 完全够用实际上 n 到 10^6 也扛得住。3.2 手推dp数组答案是怎么一步步算出来的写代码之前强烈建议在草稿纸上手推前几个值。大富翁游戏的手推过程是这样的dp[0] 1起点本身算一种dp[1] dp[0] 1dp[2] dp[1] dp[0] 1 1 2dp[3] dp[2] dp[1] dp[0] 2 1 1 4dp[4] dp[3] dp[2] dp[1] dp[0] 4 2 1 1 8dp[5] dp[4] dp[3] dp[2] dp[1] dp[0] 8 4 2 1 1 16dp[6] dp[5] dp[4] dp[3] dp[2] dp[1] dp[0] 16 8 4 2 1 1 32dp[7] dp[6] dp[5] dp[4] dp[3] dp[2] dp[1] 32 16 8 4 2 1 63。这里有个很漂亮的规律n 小于等于 6 的时候dp[n] 2^(n-1)因为前面每个格子都能一步跳到目标但到了 n7来源中不再包含 dp[0]少了一项结果就从 64 变成 63。这个手推过程特别能检验你对“来源”的理解是否正确。如果你推出来的 dp[7] 不是 63说明转移方程或边界一定有问题。我笔试现场的习惯是先在草稿纸上列 5 个左右的手算值代码写完再逐项对比。只要手算值和程序输出一致这道题大概率就稳了。手推的另一个隐藏好处是它能逼你把状态定义和边界条件真的想清楚而不是靠运气蒙对。3.3 完整代码实现C版和Python版C 版本#include iostream #include vector using namespace std; int main() { int n; cin n; vectorlong long dp(n 1, 0); dp[0] 1; // 起点本身就是一种方案 for (int i 1; i n; i) { for (int step 1; step 6; step) { if (i - step 0) { dp[i] dp[i - step]; } } } cout dp[n] endl; return 0; }Python 版本n int(input()) dp [0] * (n 1) dp[0] 1 for i in range(1, n 1): for step in range(1, 7): if i - step 0: dp[i] dp[i - step] print(dp[n])两段代码逻辑完全一致。用 long long 是有原因的方案数增长极快n40 时答案已经超过 int 的上限n47 左右就可能超过 64 位整数。如果题目要求对某个模数取模直接在累加时加一个 mod 就行。运行示例输入 7输出 63输入 3输出 4。和手推结果完全吻合。3.4 进阶优化滑动窗口与矩阵快速幂朴素递推 O(n) 的时间复杂度已经非常优秀但如果有面试官追问“还能不能更快”或者题目把 n 改成 10^9 甚至 10^18你就需要拿出进阶方案了。第一种是滑动窗口优化维护一个变量 window表示当前 i 的最近 6 个 dp 值之和。每推进一格window 加新值、减过期值时间仍然 O(n)空间降到 O(1)。实现的时候用一个长度为 6 的循环数组也可以。第二种是矩阵快速幂。把状态向量定义成 [dp[i], dp[i-1], ..., dp[i-5]]^T那么一次转移相当于左乘一个固定的 6x6 矩阵 M。求第 n 项就变成了求 M 的幂用快速幂做到 O(6^3 log n)约等于 O(log n)n 再大也不怕。这块属于进阶内容笔试很少直接考但面试官十有八九会顺着问一句“还能优化吗”提前准备绝对有备无患。实现方式时间复杂度空间复杂度适用场景朴素递推O(n)O(n)n 10^6滑动窗口O(n)O(1)n 很大但还能接受 O(n)矩阵快速幂O(log n)O(1)n 达到 10^18还是要提醒一句优化是加分项不是必选项。笔试第一优先级是过样例拿分先把基础的 O(n) 版本稳稳写对再去想扩展。我见过太多人一上来就写矩阵快速幂结果转移矩阵构造错了一位半小时全耗在上面得不偿失。4. 拼凑钱币背包计数DP的实战分析4.1 题目建模组合数还是排列数拼凑钱币这道题第一个要确认的问题是要组合数还是排列数。题意已经说得很清楚组合方式不计顺序[1,2] 和 [2,1] 算同一种所以答案是组合数。以 sum5、硬币面额 1、2、5 为例手算结果是 4 种1 1 1 1 11 1 1 21 2 25注意 112 的排序问题121、211 都和 112 是同一种组合只能算一次。这类问题本质上是完全背包的计数版每个硬币可以选任意多次但由同一种面额构成的“物品”不能区分顺序。组合计数与排列计数的关键区别不在状态定义里而在循环顺序里。很多同学状态和转移方程都写对了就栽在循环顺序上后面我会专门展开。4.2 循环顺序为什么是背包DP的生命线标准的完全背包计数核心代码是两层循环for coin in coins: for j in range(coin, sum 1): dp[j] dp[j - coin]外层循环枚举硬币面额内层循环枚举金额。这个顺序的语义是每次只考虑“当前这种面额用几个”相当于先把所有面额为 1 的方案算完再加入面额为 2 的硬币再加入面额为 5 的硬币。因为硬币是在不同阶段加入的同一种组合里的不同硬币先后顺序天然被压平了不会产生重复计数。如果把两层循环反过来写成for j in range(1, sum 1): for coin in coins: if j coin: dp[j] dp[j - coin]得到的就是排列数。举个具体的例子sum3、coins[1,2]。正确循环下 dp[3]2组合是 111 和 12 两种错误循环下 dp[3]3会多出 21 这种“颠倒顺序”的方案。多出来的那一个正是组合计数必须要去掉的。我在给同学讲这个坑时常用一个生活类比外层循环相当于先决定今天吃什么菜内层循环再决定这个菜吃几份先后顺序被合并了如果外层是金额、内层是面额就相当于每次跳转都在重新挑菜菜的上桌顺序就被当成不同方案了。循环顺序语义结果外层硬币、内层金额组合数每种面额使用次数确定顺序不计外层金额、内层硬币排列数同一种结果的不同顺序全被计数做任何背包计数题之前先确认题目要的是组合还是排列再决定循环顺序。口诀就八个字“外层物品内层容量”。这个顺序写反是背包 DP 最大的一个坑没有之一。4.3 完整代码实现与结果验证C 版本#include iostream #include vector using namespace std; int main() { int sum, m; cin sum m; vectorint coins(m); for (int i 0; i m; i) { cin coins[i]; } vectorlong long dp(sum 1, 0); dp[0] 1; // 不用任何硬币凑出 0 元算 1 种方案 for (int i 0; i m; i) { int coin coins[i]; for (int j coin; j sum; j) { dp[j] dp[j - coin]; } } cout dp[sum] endl; return 0; }Python 版本sum_money, m map(int, input().split()) coins list(map(int, input().split())) dp [0] * (sum_money 1) dp[0] 1 for coin in coins: for j in range(coin, sum_money 1): dp[j] dp[j - coin] print(dp[sum_money])这里 dp[0]1 的语义要掰扯清楚在背包计数里凑出 0 元的唯一方案是“什么都不选”这算一种方案。它是一切转移的基石写成 0 会导致整条链全为 0。这个初始化错误藏得非常深因为编译不报错、运行不崩溃就是答案全错。验证一下输入 sum5、m3、coins1 2 5程序输出 4和手算一致。4.4 背包类DP的变体思路掌握基础模型之后背包类的变体其实都是同一个骨架。变体一如果题目要求“最少用多少枚硬币凑出 sum”转移就变成 dp[j] min(dp[j], dp[j - coin] 1)初始化 dp[0]0其余为正无穷。变体二如果每种硬币有数量上限那就是多重背包问题需要在硬币循环内部再加一层数量循环或者用二进制拆分来优化。变体三如果要求输出具体方案需要额外开一个 pre 数组记录每次转移选择了哪种硬币最后从后往前回溯。这些变体看起来千变万化但核心永远逃不开“状态定义—转移—初始化—循环顺序”这四件套。我在刷题群看到不少人一个变体一个背法背得很痛苦。其实只要把基础模型吃透变体只是加维度、改转移式子而已。比如“得分计算编程题”里经常出“从起点到终点走固定步数拿最大得分”本质上就是在二维网格上做 DP状态多一个维度就能解决。5. 避坑手册秋招DP题最常见的四个坑与考场节奏5.1 翻车现场Top4与修正方案第一个坑是状态定义漏信息。大富翁游戏有人会把状态写成 dp[i] 表示“走 i 步的方案数”但题目根本没限定步数这样定义要么多算要么漏算。正确的状态是“到达第 i 格的方案数”只关心位置不关心用了多少步。我自己的检查办法是写转移前先枚举一遍“最后一步有哪些可能”把来源全列出来再写方程。来源少一个答案就会系统性变小。第二个坑是边界初始化为 0。拼凑钱币和大富翁游戏都有这个问题。有人觉得“没走到任何格子方案应该是 0”于是 dp[0]0结果所有 dp[i] 全是 0。原因很简单每个状态都依赖前驱状态源头是 0后面全断供。修正方法是先想清楚 dp[0] 的语义对于大富翁从起点到起点本身是一种方案对于拼凑钱币不用任何硬币凑出 0 元是一种方案。这两个语义一旦明确初始化就不会错。第三个坑是背包循环顺序反了前面已经重点讲过。典型现场是拼凑钱币输出比预期大很多因为把组合数算成了排列数。修正方案就一句口诀“外层物品、内层容量”。笔试时如果发现结果偏大第一时间检查循环顺序而不是怀疑取模错了。第四个坑是数据溢出。方案数是呈指数增长的大富翁 n40 时用 int 就开始出错。正确做法是看数据范围决定用 long long 还是取模。笔试题目一般会提示“答案可能很大请对 1000000007 取模”如果没提示也要默认用 long long别因为省几个字节把整题坑了。坑典型现场修正方案状态定义漏信息大富翁题把“位置”和“步数”混在一起写转移前先枚举最后一步的所有可能来源边界初始化为 0dp[0]0导致所有 dp[i] 全为 0先想清楚 dp[0] 的语义再填代码背包循环顺序反了拼凑钱币输出比预期大很多记住“外层物品、内层容量”口诀数据溢出n40 用 int答案变负数根据数据范围用 long long 或取模5.2 考场上的时间分配与自查流程一道编程题比较理想的节奏是 30 分钟左右读题 5 分钟确认数据范围和输出要求建模 10 分钟在草稿纸上写清楚状态定义、转移方程、边界条件编码 10 分钟把草稿“翻译”成代码测试 5 分钟跑样例、跑边界、跑手推的小数据。如果一道 DP 题半小时还没想出来趁早换个策略先拿部分分。自查时我按下面的顺序来先手推一个小样例比如大富翁 n3 手算结果是 4作为预期值再跑样例输入输出然后测边界比如 n1、n0、sum1、只有一种硬币最后如果结果不对优先检查初始化、循环范围、循环顺序三个点而不是从头到尾读一遍代码。这三个点就是 DP 最容易被埋雷的地方。如果完全没有思路别硬撑着写方程先写暴力递归。哪怕只能过小数据也能拿到一部分分数而且递归写完后很容易改成记忆化搜索甚至能帮你顺出递推式。另一个实用技巧是对拍笔试时间充裕时写一个暴力枚举函数和 DP 函数用随机小数据对比跑几十轮下来正确性就非常有底了。这个习惯我在平时刷题时就练考场上才能顺手就写。很多时候我后知后觉地发现动态规划刷多了就是熟练工加一点点归纳能力。我第一次看到大富翁游戏时也被 dp 数组的一堆加法吓到后来把“最后一步有哪些可能”这句话写在草稿纸最顶上状态定义就很少再写偏。美团点评这套题里大富翁考的是线性递推的边界感拼凑钱币考的是背包循环的顺序感恰好是 DP 入门最容易摔的两个位置。这篇文章把这两道题彻底拆透下次再遇到“跳台阶”“走棋盘”“换零钱”这类衍生题你至少知道往哪个方向想。最后再分享一个我自己刷题时的土习惯每做完一道 DP 题就在题号旁边写一句话解释 dp[i] 是什么、为什么从那里转移。写不出来的话说明这道题你还没真正搞懂。祝备战顺利。