2017年美团点评秋招笔试的那套编程题在当年的校招圈里流传得特别广。原因倒不是题目本身有多难而是里面几道动态规划题几乎把校招笔试最常见的DP套路一次性考了个遍乘积最大、01背包、序列得分、网格路径全都挤在同一张卷子里。我当年在牛客网上把题刷完第一感觉是“这也太狠了”后来静下心一道一道复盘才发现出题人其实很有章法。这份解题报告就是围绕这批“常见动态规划问题”整理的重点不是背答案而是把每一类题的状态定义、转移方程、边界条件和笔试现场的识别方法讲透。不管你是准备秋招的应届生还是在刷算法设计与分析期末题的学生只要能吃透这份报告里的套路应付绝大多数校招DP题基本够了。1. 为什么这届秋招的DP题值得单独写一份复盘1.1 美团点评2017秋招笔试的题型分布与DP占比先聊点背景。当时美团点评的校招笔试编程题一般是几道大题前面再配一些选择题整体题量不算小。比较狠的是编程题里动态规划类题目占了相当大的比重而且不是单独考某一种DP是把几种完全不同的状态设计模型放在同一场考试里。这意味着你光会背一个“01背包模板”是远远不够的得真的理解每个状态是“怎么想出来的”才能在考场那种压力下快速切换思路。这批题在网上流传的时候很多人的第一反应是“题目不难但我就是写不出来”。这句话听起来矛盾实际上特别真实。DP题的代码往往很短短到十几行就能AC但难的是那十几行之前的思考过程。状态定义错一个字整个转移全错转移方程里少处理一个负数的分支样例过了、提交照样WA。我后来把题目一道一道重新做了一遍整理状态设计和转移推导才发现这组题覆盖了动态规划里最核心的几类带约束的区间选择、背包决策、一维序列递推、网格路径规划。这四类恰好是校招笔试动态规划出题频率最高的方向。1.2 这组DP题的四个共同套路复盘之后我把这批题抽象成四类常见模型后面几章会逐个展开。先给一张我自己整理的对照表方便你建立整体框架题型状态定义模板关键词特征典型复杂度合唱团/带约束选择以第i个元素结尾已选j个“选k个”“相邻差不超过d”“乘积最大”O(nkd)01背包/背包变体前i个物品放入容量j的背包“重量”“价值”“容量”“方案数”O(n*W)序列型DP以i结尾 或 前i个“连续子段”“不能相邻”“最大得分”O(n) 或 O(n²)网格/路径规划到达位置(i,j)的最小/最大代价“从左上到右下”“只能向下/向右”O(m*n)这张表看着简单但每个模型在笔试题里都会换各种皮肤。比如背包题不会直接告诉你“物品重量”它可能变成“骑手的配送时间”网格路径题不会直接说“格子”它可能变成“地图上的等待时间”。所以看题的时候关键不是看表面名词而是看数据之间的约束关系。你一旦识别出“每个元素有选或不选两种决策并且有容量上限”不管它包装成什么场景脑子里的第一反应就应该是背包模型。2. 合唱团问题同时维护最大值和最小值的状态设计2.1 原题描述与第一直觉为什么是错的这道题在很多博客里都能看到题面大致是这样的有 n 个学生站成一排每个学生有一个能力值 a[i]能力值可能为负数。现在要从这 n 个学生里按顺序选出 k 个学生要求任意两个相邻被选学生的位置编号差不超过 d求选出的 k 个学生能力值的乘积最大是多少。输入范围一般给的是 n ≤ 50k ≤ 10d ≤ n。我估计很多人看到这题的第一反应是排序把所有能力值从大到小排取前 k 个乘起来不就行了这个思路分分钟被两个条件打脸。第一题目要求“按顺序选”并且相邻两个被选学生的位置差不能超过 d排序之后这个位置约束全乱了。第二能力值可能是负数排序取前 k 大只考虑了正数方向完全没处理“两个负数相乘变正数”的情况。所以这道题从一开始就必须往动态规划上走而且状态设计要同时照顾“选了几个人”和“最后一个选的人是谁”这两个维度。2.2 状态定义从“以i结尾选j个”出发我当时第一版的状态设计是 dp[i][j] 表示“前 i 个学生里选 j 个且第 i 个必须被选”的最大乘积。为什么第 i 个必须被选因为题目有相邻位置差不超过 d 的限制这个限制是针对“最后被选的那个人”和“前一个被选的人”之间的距离所以状态里必须记录最后一个被选的是谁否则下一个学生想接上来的时候你根本不知道他跟前一个被选者之间隔了多少个人。这是典型的“以 i 结尾”型 DP 状态。但只维护最大乘积还不够。这里有个非常容易踩的坑如果 a[i] 是负数最大乘积乘以一个负数会变成最小乘积反过来之前的最小乘积可能是一个很大的负数乘以一个负数反而可能变成最大的正数。举个最简单的例子前两个能力值是 -5 和 -4k2最大乘积显然是 20这个结果只能由“两个负数相乘”得到。你只维护最大乘积-4 这个分支根本不会进入候选。所以必须同时开两个数组fMax[i][j] 表示以第 i 个学生结尾、选了 j 个时的最大乘积fMin[i][j] 表示同样条件下的最小乘积。这样每次转移时把 a[i] 分别乘到上一轮的最大值和最小值上取最大和最小就能完整覆盖正负号变化。2.3 转移方程推导与负数的处理状态定义清楚了转移方程就是自然推出来的。对 fMax[i][j] 来说它的前一个状态是“以第 p 个学生结尾、选了 j-1 个”其中 p 必须满足 p i 且 i - p ≤ d。候选值有两个fMax[p][j-1] * a[i]fMin[p][j-1] * a[i]fMax[i][j] 取这两个候选值中的较大者fMin[i][j] 同理取较小者。初始化比较好办选 1 个人的时候fMax[i][1] fMin[i][1] a[i]。最后的答案就是所有 fMax[i][k] 里的最大值。这里有一个笔试常见的坑初始化数组时不要用 0因为能力值可能是负数而且乘积可能非常大。我习惯用 float(inf) 和 float(-inf)或者 C 里用 LLONG_MAX / LLONG_MIN。更稳妥的做法是在转移前判断上一层的状态是否已经被更新过避免把“未计算的非法状态”乘进去污染结果。2.4 笔试可用的Python实现与复杂度分析我当时用 Python 写了一个版本跑下来完全能过笔试的数据范围def solve(n, a, k, d): neg_inf float(-inf) pos_inf float(inf) fmax [[neg_inf] * (k 1) for _ in range(n)] fmin [[pos_inf] * (k 1) for _ in range(n)] for i in range(n): fmax[i][1] a[i] fmin[i][1] a[i] for i in range(n): for j in range(2, k 1): for p in range(max(0, i - d), i): if fmax[p][j - 1] ! neg_inf: fmax[i][j] max(fmax[i][j], fmax[p][j - 1] * a[i]) fmin[i][j] min(fmin[i][j], fmax[p][j - 1] * a[i]) if fmin[p][j - 1] ! pos_inf: fmax[i][j] max(fmax[i][j], fmin[p][j - 1] * a[i]) fmin[i][j] min(fmin[i][j], fmin[p][j - 1] * a[i]) return max(fmax[i][k] for i in range(n))复杂度是 O(n * k * d)因为状态数是 nk每个状态要枚举不超过 d 个前驱。n≤50、k≤10、d≤50 的话这个复杂度完全够用。空间上开两个 n(k1) 的二维数组也毫无压力不需要做滚动数组优化。要注意的是乘积可能会很大如果用 C 写请一定开 long long用 int 很容易在测试数据上溢出Python 没有这个问题但你要是做 C 语言编程题long long 是必须养成的习惯。提示笔试里遇到“乘积最大/最小”的DP题第一反应先想负负得正这就是为什么要同时维护最大值和最小值数组。3. 01背包及其变体从“每样东西只拿一次”到“求方案数”3.1 经典01背包的状态与转移美团作为本地生活服务平台出背包题的时候特别喜欢套“配送”和“订单”的场景。比如给你一堆订单每个订单有重量和收益骑手有一个最大载重问在载重限制内最多能获得多少收益。脱掉这层业务外壳就是最经典的 01 背包。状态定义是 dp[i][j] 表示前 i 个物品放入容量为 j 的背包能获得的最大价值。转移考虑第 i 个物品拿或不拿不拿dp[i][j] dp[i-1][j]拿dp[i][j] dp[i-1][j-w[i]] v[i]两者取最大就行。这个转移的本质是每个物品只有“选”和“不选”两种决策并且不能重复选同一个物品。这就是 01 背包和完全背包的本质区别识别清楚这一点后面才不会在迭代方向上翻车。3.2 一维滚动数组迭代方向为什么必须倒序空间优化是 01 背包的必经之路。观察转移方程dp[i][j] 只依赖 dp[i-1][...]所以完全可以用一维数组原地更新。问题在于一维数组更新容量 j 时必须从大到小遍历。我用一个特别直白的例子解释这个“为什么”。假设只有一个物品重量是 1价值是 10背包容量是 2。如果正序更新j1 时dp[1] max(dp[1], dp[0]10) 10j2 时dp[2] max(dp[2], dp[1]10) 20发现了吗dp[2] 用的 dp[1] 已经是本轮更新过的值里面已经包含了这个物品。这意味着同一个物品被拿了两次结果直接变成完全背包的答案。倒序遍历就不会有这个问题j2 时用的 dp[1] 还是上一轮的值这个物品只被考虑一次。笔试的时候我不止一次看到有人把方向写反样例还能过一到大数据就 WA非常折磨人。所以这个倒序一定要当成肌肉记忆。def zero_one_knapsack(weights, values, W): dp [0] * (W 1) for w, v in zip(weights, values): for j in range(W, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[W]3.3 笔试常见三种变体恰好装满、方案数、余数约束美团这类公司的笔试不会只考裸的 01 背包变体才是重头戏。我在刷题时遇到过三种高频变体这里一次性说清楚。第一种是“恰好装满”的背包。经典背包的 dp[j] 初始化为 0表示容量没装满也能得到价值 0但题目如果要求背包正好装满初始化就不同了dp[0] 0其他 dp[j] float(-inf)。这样转移时dp[j-w[i]] 是 -inf 的话说明凑不出“恰好装满 j-w[i]”的状态自然不能用来转移。这个技巧也适用于求“恰好凑出某个金额的最小/最大花费”。第二种是“求方案数”。给定一组物品重量问有多少种方案能装满容量 W。转移方程从取 max 换成求和dp[j] dp[j-w]。初始化 dp[0] 1表示空方案也是一种方案。注意这类题如果物品视为不同个体用 01 背包模板如果物品可以无限用就按完全背包正序遍历。第三种是“余数约束”。有些题不问你最大价值而是问选出来的总重量对某个数取模后最大是多少或者你能不能凑出一个重量模 M 等于某值。这种题的核心思路是改变背包的“容量维度”把 j 从“真实容量”改成“容量对 M 的余数”转移时用 (j w) % M 作为新状态。这个变体在算法设计与分析期末题里也很常见算是同一个套路在不同场景下的复现。3.4 Python实现模板与数据范围判断笔试时拿到背包题我建议先做一件事看 W 的范围。如果 W 是 10^5 以内、n 是 10^3 以内直接用 O(n*W) 的背包。如果 W 到了 10^9背包这条路基本走不通大概率要用贪心、二分答案或者把所有物品按性价比排序之后做部分背包。还要看物品数量。n 很小但 W 很大时可以考虑折半枚举Meet in the Middle把 n 拆成两半分别枚举所有组合再合并。这个方法在 n≤30 时很实用复杂度从 O(n*W) 降到 O(2^(n/2) * poly)。但说实话校招笔试碰到这种极端数据范围的概率不高真正的重点还是先把基础背包写熟练。4. 序列型DP的两种状态模板“以i结尾”还是“前i个”4.1 最大子段和与打家劫舍的对比序列型 DP 是笔试里最基础也最好用的题型美团 2017 那批题里也有类似“得分计算编程题”的版本。典型题面是一行格子每个格子上有一个分值现在要选一些格子拿分限制是不能同时选相邻两个格子问最大能拿多少分。这题在 LeetCode 上叫“打家劫舍”核心思路非常清晰用 dp[i] 表示前 i 个格子能拿到的最大分数第 i 个格子只有拿和不拿两种选择拿得分是 dp[i-2] a[i]不拿得分是 dp[i-1]代码很短def rob(a): n len(a) if n 0: return 0 if n 1: return a[0] dp [0] * n dp[0] a[0] dp[1] max(a[0], a[1]) for i in range(2, n): dp[i] max(dp[i - 1], dp[i - 2] a[i]) return dp[n - 1]这个“前 i 个”模板的关键是答案只关心前 i 个位置的最优值不关心最后一个被选的位置具体在哪。它和“以 i 结尾”模板的分界点就在这里。再看另一个经典题最大连续子段和。这题的状态定义是 dp[i] 表示“以第 i 个元素结尾的最大连续子段和”转移是 dp[i] max(a[i], dp[i-1] a[i])。为什么不直接用“前 i 个元素的最大子段和”因为连续子段有“必须在当前位置结束”的要求你只有知道以 i-1 结尾的子段和才能判断接上 a[i] 之后是变大还是变小。如果不用“以 i 结尾”直接做“前 i 个元素的最大子段和”转移时根本不知道上一个子段从哪里开始也就没法保证“连续”这个约束。所以我的经验是遇到有“连续”“相邻”“结尾”这类约束的题优先考虑“以 i 结尾”遇到只问全局最优、不关心末尾位置的题用“前 i 个”模板。4.2 LIS的O(n log n)优化什么时候值得写最长递增子序列LIS是序列型 DP 里的常客。基础思路是 dp[i] max(dp[j] 1)其中 j i 且 a[j] a[i]复杂度 O(n²)。n 比较小的时候这写法完全没问题代码也直观。但 n 一旦超过 5000O(n²) 就开始吃力了这时候需要换用二分优化。二分优化的核心是维护一个 tails 数组tails[len] 表示长度为 len 的递增子序列中末尾元素的最小值。这个数组是单调递增的所以可以二分查找第一个大于等于 a[i] 的位置把它替换成 a[i]相当于用一个更小的末尾值“更新”了该长度的潜力。代码长这样def length_of_lis(a): tails [] for x in a: l, r 0, len(tails) while l r: mid (l r) // 2 if tails[mid] x: l mid 1 else: r mid if l len(tails): tails.append(x) else: tails[l] x return len(tails)笔试时要不要写二分优化我的判断标准是看数据范围n ≤ 2000 直接 O(n²) 更省心n ≥ 10^4 再上二分。还有一种情况是题目不仅要求长度还要求输出具体递增子序列这时候纯 tails 二分就不好使了需要额外记录前驱数组。面试里如果被追问这个问题能把 O(n²) 的打印路径写法讲清楚其实已经足够加分。4.3 得分计算类题目的通用拆解步骤把“得分计算编程题”这类问题做一个统一拆解以后遇到就不会慌。我一般按三个步骤走。第一步识别约束条件。题目说“不能相邻”那转移里就要出现 i-2题目说“不能选超过 k 个”那状态里就要加一维 j 表示已选数量题目说“连续段长度不能超过 L”那状态可能是“以 i 结尾、长度为 len”。第二步确定状态模板。先问自己一个问题转移的时候需不需要知道前一个被选的元素是哪个如果需要用“以 i 结尾”型如果不需要用“前 i 个”型。这一点想清楚后面就不会写出错的状态。第三步补齐边界。很多一维 DP 的坑都出在 i0 和 i1 这两个初始位置。比如打家劫舍这种需要 dp[i-2] 的状态i0 和 i1 必须单独初始化否则下标直接越界。笔试的时候我习惯先把数组长度等于 0、1、2 的边界样例手算一遍再提交能省去很多无谓的 WA。5. 车辆调度与网格路径类DP把业务场景还原成状态转移5.1 网格最短路与带障碍物处理美团 2017 年已经在做配送和出行相关的业务所以笔试里出“车辆动态规划问题”是很自然的事。这种题到算法层面往往就变成网格路径类 DP核心模型是一个 m×n 的网格每个格子有一个代价比如等待时间一辆车从左上角出发每次只能向右或向下移动最终到达右下角求最小总代价。状态定义很直接dp[i][j] 表示到达位置 (i, j) 的最小代价。因为只能向右和向下走所以 (i, j) 的上一个位置只可能是 (i-1, j) 或 (i, j-1)转移就是取这两个来源的最小值加上当前格子的代价def min_path_sum(grid): m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] for j in range(1, n): dp[0][j] dp[0][j - 1] grid[0][j] for i in range(1, m): dp[i][0] dp[i - 1][0] grid[i][0] for i in range(1, m): for j in range(1, n): dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j] return dp[m - 1][n - 1]这类题的高频变体是“带障碍物”。比如网格里某些格子不可通行直接把障碍物格子的 dp 值设成无穷大即可。另一种变体是把“最小代价”改成“最大得分”转移从 min 换成 max逻辑完全一样。还有一种是问有多少条不同路径能到达终点这时 dp 存的是方案数转移变成 dp[i][j] dp[i-1][j] dp[i][j-1]障碍物格子的 dp 值设为 0。5.2 空间优化从二维到滚动数组网格路径类问题的二维 DP 在 m 和 n 都很大时会吃掉不少内存。其实这类题也能像 01 背包一样做空间优化用一维滚动数组代替二维数组。核心思路是逐行扫描时dp[j] 在更新前代表上一行第 j 列的值更新后代表本行第 j 列的值。转移写成 dp[j] min(dp[j], dp[j-1]) grid[i][j]。这里的 dp[j] 是上一行的值相当于 dp[i-1][j]dp[j-1] 是本行刚刚更新的值相当于 dp[i][j-1]。所以 j 要从左往右遍历这和 01 背包的倒序遍历正好相反。理解这个方向性的差别比死记硬背重要得多。需要注意的是滚动数组虽然省空间但可读性会下降。笔试时如果内存限制不紧张我通常还是写二维数组因为二维版本更直观、更容易 debug。等代码通过样例之后再根据内存限制决定要不要优化。5.3 “不好好DP的车辆问题”可能是贪心或最短路这里我要特别提醒一个反套路。有些题目表面上是“车辆动态规划”但最优解根本不是动态规划而是贪心或最短路。比如“汽车从起点出发油箱容量有限途中经过若干加油站每个加油站有不同油价求最小加油费用”——这种题的正确解法是贪心加优先队列你每到一个加油站都把当前油量能到达的站维护进来按价格排序取最低价而不是开一个二维 DP。为什么容易混淆因为这类题也有“最优子结构”和“决策选择”这些特征但它的选择对象是动态变化的每一步都在根据当前资源做局部最优决策。DP 处理的是“状态之间有固定转移关系”的问题而加油站的场景里油价、剩余油量、当前位置三个变量组合起来会让状态爆炸DP 的复杂度根本扛不住。所以笔试时先别急着套 DP先看状态空间的大小如果状态数是指数级或者超过可接受范围大概率要换思路。我之前整理过一份简单的判断逻辑网格、序列、背包、区间这些问题状态是线性或二维的适合 DP而涉及“动态资源的实时分配”“区间选择优先级”这类问题多想想贪心、堆、最短路。这不算什么高深理论但能在考场帮你节省大量时间。6. 笔试现场如何快速识别DP题并做好时间分配6.1 三步识别法最优子结构、重叠子问题、状态可定义到了实战环节最怕的不是题目难而是“明明会做但看不出来是 DP”。我总结了一个三步识别法每次遇到新题都按这个顺序过一遍。第一步看有没有最优子结构。把原问题缩小成子问题如果子问题的最优解能直接组合出原问题的最优解那就有 DP 的潜质。比如“最大连续子段和”子问题是“以 i-1 结尾的子段和”接上 a[i] 就能得到原问题的一部分。第二步看有没有重叠子问题。画一棵递归树如果同样的子问题在递归过程中被反复计算那就不该用递归要用 DP 记忆化。这也是为什么很多人第一反应写递归会超时改成 DP 就过了。第三步给状态一个定义。状态本质上是“为了让后续决策不再依赖历史信息我需要记住哪些变量”。合唱团问题要记住“最后一个选的人是谁”和“选了几个”背包问题要记住“当前剩余容量”网格问题要记住“当前坐标”。如果这几个变量能被有限个整数表示DP 就成立。6.2 边界条件自查清单动态规划代码写出来之后我建议先别急着提交按下面这个清单逐一检查数组下标有没有越界。尤其是用到 dp[i-2]、dp[j-w[i]] 这类表达式时确认 i 和 j 的起始位置已经把边界下标算进去了。初始化值对不对。求最大值用负无穷求最小值用正无穷求方案数用 0 或 1这些不要混。数据范围有没有超类型。乘积题用 long long加法题看会不会溢出 int。空数组、单元素数组能不能直接返回。很多题对这些特殊输入要单独处理。转移顺序对不对。01 背包倒序遍历完全背包正序遍历滚动数组的遍历方向跟状态依赖关系严格对应。这些坑单个看都很傻但在考场上高度紧张的状态下是最容易翻车的地方。我自己的做法是在写完代码后先用题目给的样例跑一遍再自己构造一个最小样例手算验证最后再提交。这个过程大概多花两分钟但能避免大量无意义的罚时。6.3 从暴力递归到记忆化再到DP的应试策略笔试时的心态是“先求能过再求最优”。如果一个 DP 题在五分钟内直接想到最优解那就直接写如果卡住了我推荐一条保守路线先写暴力递归再改成记忆化搜索最后再优化成真正的 DP。为什么这条路线值得推荐因为暴力递归是最符合人的直觉的写法几乎不可能写错。比如说“从网格左上走到右下求最小代价”递归版本就是 search(i, j) min(search(i-1, j), search(i, j-1)) grid[i][j]逻辑和题目描述一模一样。等递归写出来了你自然会看到重叠子问题然后用一个 memo 字典把已经算过的状态存下来这就是记忆化搜索。在某些数据范围比较温和的笔试题里记忆化已经能 AC 了。记忆化再往下走一步就是把它改成迭代的 DP 数组。这一步对很多人来说其实更难因为要处理初始化、遍历顺序这些细节。所以如果时间紧直接把记忆化版本提交也是一种务实的策略。我见过不少考生花二十分钟把 DP 优化出来最后因为一个顺序错误反复 WA反而不如一开始就提交记忆化版本拿稳分数。当然如果数据范围明确说明 O(n²) 会超时那还是得咬牙写优化版。6.4 复盘方法我的状态设计卡片习惯最后分享一个我自己的学习方法。每次刷完一批 DP 题我不会只把代码存起来而是会做一套“状态设计卡片”每张卡片只有三个部分题目类型、状态定义、转移方程。比如合唱团问题的卡片写“带约束选择型dp[i][j] 以 i 结尾选 j 个转移枚举前驱 p同时维护 max/min”01背包的卡片写“决策型dp[j] 前 i 个物品容量 j倒序更新”。这套卡片不需要整理成多精美的文档能让自己看懂就行。关键是笔试前翻一遍卡片相当于把几大类 DP 的状态设计重新过了一遍比临时刷几道题有用得多。对我来说刷完这批题最大的收获不是会做某几道题而是建立了一种“见到 DP 题先想状态而不是先想题解”的本能。这份本能恰恰是秋招笔试里最值钱的东西。