企业官网建设流程全解析

说实话，秋招笔试里最怕遇到什么题？我猜很多人会脱口而出：动态规划。美团点评2017秋招笔试的编程题里，动态规划几乎是绕不开的坎，不管是前端、后端还是算法岗，卷子上总有一两道题在等着你。这玩意儿不像链表反转或者快排，背一背模板就能写出来，它考的是你对问题结构的理解，对状态的抽象能力，以及对边界条件的敏锐度。很多人刷题刷到一定程度会发现，动态规划题永远有新花样，换个场景就不会做了。

今天这篇解题报告，我就把当年秋招笔试里动态规划题的常见考法、解题套路和踩坑经验拆开揉碎了讲一遍。不整虚的，直接上方法论和代码，每个题我都会从最原始的暴力思路讲起，一步步推导到动态规划解法，文末还会附上笔试现场的时间分配和调试技巧。不管你是正在准备秋招的应届生，还是想系统补一补DP基础的后端开发，这篇文章都能给你一个相对完整的参考框架。

1. 动态规划题为什么在秋招笔试里如此高频

先说个很多人没想明白的问题：面试官难道不知道动态规划难吗？他当然知道。正因为难，才更要考。笔试的目的是在短时间内筛选出算法基础扎实、思维成体系的人，而动态规划恰好能同时考察三件事：读题归纳能力、逻辑推导能力、代码实现能力。一道设计良好的DP题，暴力解法和最优解法之间的代码量可能相差不大，但思考深度完全不在一个层次。

另一个现实因素是，动态规划的应用范围太广了。字符串匹配、路径规划、资源分配、序列预测，几乎所有和优化沾边的业务场景，底层都能抽象出DP模型。美团点评的业务里，外卖配送路径规划、推荐系统里的序列建模、调度系统里的资源分配，背后都有动态规划的影子。公司招人，自然倾向于筛选能解决这类问题的人。

从题目分布来看，秋招笔试的动态规划题大致集中在几个固定类型：线性序列DP（最长递增子序列、最大子段和）、区间DP（石子合并、回文串分割）、背包类DP（01背包、完全背包）、双序列DP（最长公共子序列、编辑距离）、状态压缩DP（旅行商问题）。把这些经典模型吃透，笔试时80%的DP题都能套上对应的框架。

1.1 什么样的问题才适合用动态规划

判断一道题能不能用DP，很多人只看“最优解”三个字，其实不够。动态规划能解决的问题必须同时具备三个特征：最优子结构、重叠子问题、无后效性。

最优子结构的意思是，整个问题的最优解包含子问题的最优解。比如求从起点到终点的最短路径，如果最优路径经过中间点A，那么从起点到A的这段也一定是最短的，否则可以用更短的一段替换，从而得到更短的完整路径。这是动态规划成立的前提。

重叠子问题是指，递归求解时同一个子问题会被反复计算无数次。举个最简单的例子，计算斐波那契数列的第n项，朴素递归是一个指数级的过程，但子问题的数量只有n个，大量计算是重复的。动态规划的核心优化点就在这里——用空间换时间，把子问题的结果存起来，避免重复计算。

无后效性可能让很多人头疼，其实理解起来不复杂：某个状态一旦确定，就不受后续决策的影响。也就是说，我只需要关心当前状态是什么，不需要关心这个状态是怎么一步步走过来的。比如背包问题里，我只需要知道当前剩余容量是多少，而不需要知道哪些物品被装进去了。如果一道题要求你完整记录路径，那就不能直接用普通DP，需要额外维护一个回溯数组。

1.2 动态规划解题五步法

第一，明确状态。这一步最关键，状态定义直接决定了转移方程的复杂度和代码的清晰度。笔试时如果状态定义得好，整个题目就做对了一半。第二，确定状态转移方程。这是核心，把大问题拆成小问题，用数学式子表达出“从已知状态推未知状态”的关系。第三，确定初始化和边界条件。很多代码出错，不是转移方程写错，而是初始化没写对。第四，确定计算顺序。保证计算某个状态时，它依赖的状态已经全部算出来了。第五，复杂度优化。空间维度能不能压成一维，时间上能不能用单调队列或前缀和加速。

这套流程看起来简单，但每一步都有坑。后面我会结合具体题目逐条演示。

2. 笔试中最高频的三类动态规划题型盘点

先给一个整体认知：秋招笔试的DP题虽然多，但模型就那么几类。把每一类的状态定义方式和转移方程背熟，再通过题目练习内化成自己的东西，比你盲目刷几百道题有用得多。

2.1 线性序列类：从最长递增子序列说起

线性序列DP是最基础的一类，特征是在一个序列上从左到右或者从右到左进行递推。典型题目有最大子段和、最长递增子序列、乘积最大子数组、打家劫舍系列。

我们拿最长递增子序列（LIS）来说。状态定义是dp[i]表示以第i个元素结尾的最长递增子序列长度。转移方程是dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。初始化把所有dp[i]设为1，因为每个元素本身可以单独构成一个长度为1的递增子序列。这是一个O(n^2)的解法，笔试写这个复杂度基本够用。如果数据范围到10^5，需要优化到O(n log n)，用贪心加二分维护一个递增数组，但这属于进阶技巧，笔试一般不强制要求。

最大子段和就更有意思了，状态定义是dp[i]表示以第i个元素结尾的最大子段和，转移方程是dp[i] = max(nums[i], dp[i-1] + nums[i])。翻译成人话就是：要么从当前元素重新开始一段，要么把当前元素接到前面的段上。这个题目特别适合用来理解“无后效性”——dp[i]只关心以i结尾的子段和，不关心这段是怎么组成的。

2.2 背包类：01背包和完全背包的核心差异

背包问题是笔试里最常被拿来“换皮”的模型，美团点评的笔试题特别喜欢把背包包装成各种业务场景。比如你有m元的优惠券，要在n种商品里选一些购买，每种商品只能用一次，求能获得的最大积分——这就是标准的01背包。把“只能用一次”改成“能用无限次”，就成了完全背包。

01背包的状态定义是dp[i][j]表示前i个物品，在容量为j的背包里能装下的最大价值。转移方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。完全背包的转移方程看起来几乎一样，只是把dp[i-1][j-w[i]]换成dp[i][j-w[i]]。这个细微的区别，应用在一维滚动数组上时就成了那个著名的“01背包逆序遍历，完全背包正序遍历”的结论。

2.3 双序列类：最长公共子序列和编辑距离

双序列DP是秋招笔试的压轴常客，美团点评的笔试里出现频率很高。状态定义一般是一个二维数组dp[i][j]，表示第一个序列的前i个元素和第二个序列的前j个元素之间的某个最优值。

以最长公共子序列（LCS）为例，转移方程是：当s1[i-1] == s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这个转移方程的推导逻辑很直观：两个字符相等，那它们必然可以作为公共子序列的一部分；不相等时，至少有一个字符不在最优解里，那就取去掉一个字符后的较大值。

编辑距离比LCS多了一个替换操作，转移方程变成长这样：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)，其中cost在s1[i-1] == s2[j-1]时为0，否则为1。这三个候选值分别对应删除、插入、替换三种操作。这个题目在业务场景里的应用非常广泛，比如搜索引擎的拼写纠错、DNA序列比对，都是编辑距离的变体。

为了方便读者对比，我把这几类模型整理成一个表格：

3. 一道题吃透动态规划的完整推导过程

纸上谈兵没有意义，我拿一道笔试里出场率极高的经典题来完整演示一遍思考过程：数字三角形。这题在美团点评的面试题里出现过类似版本，也是很多高校算法课上必讲的入门题。

题目是这样的：给定一个数字三角形，从顶部出发，每次只能移动到下一层相邻的节点上，求从顶部到底部的最大路径和。相邻指的是下一层中和当前位置下标相同或者下标加一的节点。

第一眼看这道题，暴力做法是枚举所有路径。第n层有n个节点，从顶部到底部有2^(n-1)条路径，这个复杂度直接爆炸。接下来思考能不能用动态规划。问题具有最优子结构：从顶部到某个节点的最大路径和，等于从顶部到它上一层相邻节点的最大路径和，加上当前节点的值——因为路径只能从上往下走，到当前节点的最后一步必然是从左上或右上来的。这也很自然地带出了状态定义：dp[i][j]表示从顶部走到第i层第j个节点的最大路径和。

状态转移方程就是dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j])。注意j-1可能越界，j也可能等于i越界，需要单独处理。初始化时dp[0][0] = triangle[0][0]。计算顺序从上往下逐层推进，最后答案是最后一层所有dp值的最大值。

代码实现上，一般有两个版本。第一个版本是直接用二维数组存dp值，非常直观：

def max_path_sum(triangle): n = len(triangle) dp = [[0] * n for _ in range(n)] dp[0][0] = triangle[0][0] for i in range(1, n): for j in range(i + 1): if j == 0: dp[i][j] = dp[i-1][j] + triangle[i][j] elif j == i: dp[i][j] = dp[i-1][j-1] + triangle[i][j] else: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] return max(dp[n-1])

第二个版本是空间优化，注意到dp[i]只依赖dp[i-1]，可以用滚动数组把空间压到O(n)。更极端的做法是直接在原数组上原地修改，从下往上递推，最后dp[0][0]就是答案。笔试时如果你对空间没要求，直接用二维数组最稳妥，不容易出错；追求代码简洁或者内存紧张时再用优化版本。

这个题目最典型的错误有三类：一是不处理边界条件，导致数组越界；二是把max写成了min，审题不仔细；三是初始化漏了dp[0][0]，导致整个递推结果全错。笔试时遇到这种看起来基础的题，反而要提醒自己慢下来。

4. 01背包问题的详细拆解：从二维DP到一维优化

背包问题是所有动态规划题里最值得深入研究的题型。原因是它够经典，变体够多，而且美团点评的笔试特别爱把背包问题包上一层业务外壳。你看热搜词里有“01背包动态规划python”，说明这个考点在求职者中关注度相当高。

我用一个贴近实际业务的场景来描述这道题：你在美团外卖上有很多张满减券，手上的余额是B元，现在有n种商品，第i种商品的价格是price[i]，积分价值是score[i]，每件商品只能买一次，问在预算内能获得的最大积分是多少？这个外壳去掉，本质就是01背包。

状态定义写出来：dp[i][j]表示前i个商品，在不超过j元预算的情况下能获得的最大积分。转移方程的推导逻辑是，对于第i个商品，你有两个选择：不买它，那最大积分就是dp[i-1][j]；买它，那需要腾出price[i]的预算，剩余预算j-price[i]分给前i-1个商品，积分是dp[i-1][j-price[i]] + score[i]。两者取大即可。

下面给出Python实现，这也是热搜词里大家最常用的语言：

def max_score(n, budget, price, score): # 初始化二维dp数组，dp[i][j]表示前i件商品预算j能获得的最大积分 dp = [[0] * (budget + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(budget + 1): if j >= price[i-1]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-price[i-1]] + score[i-1]) else: dp[i][j] = dp[i-1][j] return dp[n][budget]

这个解法的时间和空间复杂度都是O(n*budget)，当n和budget都为10^3量级时，空间消耗接近10^6，还在可接受范围内。但如果数据范围更大，就要用一维滚动数组压缩空间。

一维优化的思路是去掉第一维，直接用dp[j]表示预算为j时的最大积分。关键点在于内层循环必须从budget往0方向逆序遍历。原因在于：如果正序遍历，dp[j-price[i]]可能在当前这一轮已经被更新过了，这会导致同一个商品被重复选择多次，等价于完全背包。而逆序遍历保证dp[j-price[i]]使用的还是上一轮的状态，符合01背包“每件物品只能选一次”的约束。

def max_score_1d(n, budget, price, score): dp = [0] * (budget + 1) for i in range(n): # 必须逆序，防止重复选同一个商品 for j in range(budget, price[i]-1, -1): dp[j] = max(dp[j], dp[j-price[i]] + score[i]) return dp[budget]

笔试时这块有一个高频追问点：如果要求“恰好花完预算”怎么改？思路是把dp数组初始化为负无穷，只把dp[0]设为0，这样所有从非法状态转移过来的值都会保持负无穷，最后dp[budget]如果还是负无穷，说明无法恰好凑齐预算。这个技巧在很多变种题里都会用到。

还有一个常见变种是求方案数，比如“有多少种方案可以凑出预算B”。这时状态定义dp[j]表示凑出预算j的方案数，转移方程改成dp[j] = dp[j] + dp[j-price[i]]，同样需要逆序遍历。注意初始化dp[0] = 1，因为是“空方案”。这个题目在外卖业务里就对应“有多少种满减组合方式”，很贴近实际。

注意：01背包的逆序遍历不是死记硬背的结论，而是从二维状态转移中推导出来的必然结果。面试时如果被问到为什么，你要能从dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)出发，解释清楚一维数组在正序和逆序时的覆盖顺序差异。

5. 最长公共子序列与编辑距离：双序列DP的黄金搭档

双序列动态规划在秋招笔试里属于“见之则喜，见之则忧”的题。喜的是模型固定，只要做过几道题就能一眼识别；忧的是状态设计一旦想错，整个代码就废了。这一节把最长公共子序列（LCS）和编辑距离（Edit Distance）放在一起讲，因为它们的思路高度相似，学会一个就能触类旁通。

先看LCS。问题是给定两个字符串s1和s2，求它们的最长公共子序列长度。注意子序列不要求连续，但要求保持相对顺序。状态定义dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列长度。

转移逻辑分两种情况讨论。当s1[i-1] == s2[j-1]时，这两个字符可以拼到公共子序列的末尾，所以dp[i][j] = dp[i-1][j-1] + 1。当字符不相等时，当前这两个字符不能同时出现在公共子序列里，那就看舍掉哪一个更优，取dp[i-1][j]和dp[i][j-1]里的较大值。这就是转移方程的全部内容。

def lcs(s1, s2): n, m = len(s1), len(s2) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if s1[i-1] == s2[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[n][m]

这道题的代码很简单，但笔试的坑往往不在代码本身，而在题意理解。“最长公共子序列”和“最长公共子串”是两回事，子串要求连续，转移方程必须改成：字符相等时dp[i][j] = dp[i-1][j-1] + 1，字符不等时dp[i][j] = 0。这个改动的本质是，一旦出现不匹配，连续的公共部分就被打断了，只能清零重新计数。很多人在笔试里把这两个概念混了，导致整道题白写。

编辑距离的问题描述更贴近真实业务：允许对字符串做插入、删除、替换三种操作，求把s1变成s2的最少操作次数。状态定义仍然是dp[i][j]，表示s1前i个字符变成s2前j个字符的最少操作次数。

转移方程的推导比LCS多一步：考虑最后一步操作可以是删除、插入、替换三种。删除对应dp[i-1][j] + 1，意思是s1的第i个字符不要了，直接用前i-1个字符去匹配s2的前j个；插入对应dp[i][j-1] + 1，意思是在s1的末尾插入一个字符来匹配s2的第j个字符；替换对应dp[i-1][j-1] + cost，如果s1[i-1]和s2[j-1]已经相等，cost为0，不用操作，否则cost为1。三者取最小值。

def edit_distance(s1, s2): n, m = len(s1), len(s2) dp = [[0] * (m + 1) for _ in range(n + 1)] # 初始化：空字符串到任意字符串的操作次数 for i in range(n + 1): dp[i][0] = i for j in range(m + 1): dp[0][j] = j for i in range(1, n + 1): for j in range(1, m + 1): cost = 0 if s1[i-1] == s2[j-1] else 1 dp[i][j] = min( dp[i-1][j] + 1, # 删除 dp[i][j-1] + 1, # 插入 dp[i-1][j-1] + cost # 替换或跳过 ) return dp[n][m]

初始化这块特别容易错。dp[i][0]表示把s1前i个字符变成空字符串，只能靠删除，所以要初始化为i。dp[0][j]同理初始化为j。很多代码跑出来结果偏小，就是初始化全设成0导致的。这个教训我记得特别清楚，之前给一个学弟Review代码，他无论如何都找不出编辑距离结果比预期小1的原因，最后发现问题就出在初始化行。

双序列DP还有一个通用优化技巧：滚动数组。因为dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]这三个状态，所以可以用两行数组交替滚动，把空间从O(n*m)压到O(m)。但注意，dp[i][j-1]是当前行的状态，dp[i-1][j]和dp[i-1][j-1]是上一行的状态，滚动时需要用变量把左上角的值提前保存下来，否则会被覆盖掉。笔试时如果内存限制不严格，我建议直接用二维，把精力放在逻辑正确性上。

6. 笔试现场避坑指南：动态规划题的常见错误与调试技巧

动态规划题从框架搭建到代码通过，中间的坑比想象中多得多。这一节我把自己在笔试、面试和日常刷题中踩过的坑集中整理一遍，全部是实战经验，不是教科书里的“建议”。

6.1 三个最容易翻车的初始化错误

第一个错误是dp数组的维度搞错。做双序列DP时，dp数组应该是(n+1)行(m+1)列，多出来的那行那列用来表示空序列。很多人习惯直接用n和m作为维度，结果遍历时从1开始就越界了。

第二个错误是初始化的值不对。求最小值的问题，dp数组通常初始化成无穷大；求最大值的问题，初始化成0或者负无穷。这个逻辑本身不难，难的是搞清楚边界状态应该怎么设。比如编辑距离里的dp[i][0] = i，这是“删掉所有字符”的意思，不能设成0也不能设成无穷大。

第三个错误是忘记处理空输入。字符串可能为空、数组可能长度为0，这些边界情况在笔试的隐藏测试用例里一定会出现。写代码时第一行就应该考虑：n == 0时应该返回什么？我见过太多人代码逻辑全对，就因为没处理空数组导致一个用例超时或者报错。

6.2 动态规划调试的四个实用技巧

第一，小规模暴力对拍。笔试的时候没有本地环境，但在平时练习时，我强烈建议先写一个递归暴力版本，再写DP版本，用随机小规模数据对比两者结果。这个方法能定位到90%以上的逻辑错误，效率远高于人脑模拟。

第二，打印dp表。当DP结果不对时，把dp数组完整打印出来，逐行检查初始化是否正确、转移是否按预期进行。特别是二维DP，打印出来的表格一眼就能看出哪些状态的值不合理。

第三，单步追踪关键状态。选取一个具体的测试用例，手动计算几个关键状态的期望值，和程序输出的dp表对比。比如01背包问题，手动算一遍dp[3][5]应该是多少，再回头看代码为什么算出来不一样。

第四，边界用例优先测试。在写完代码后立刻用n=1、n=2、all相同元素、逆序输入这几个用例自测一遍。大多数DP代码在边界用例上都会暴露问题，比你自己随机造数据管用。

6.3 常见问题速查表

7. 笔试现场的实战策略：如何规划时间与表达思路

最后聊点笔试时的时间管理和解题策略。很多人遇到动态规划题，第一反应是“完了，我不会”，然后开始乱试。实际上，即使你对这道题没有完全的把握，也能通过规范的思考过程拿到大部分分数。

读题阶段建议控制在3到5分钟。这段时间不写代码，只做三件事：确定输入输出格式、判断问题是否具备最优子结构、尝试把题目映射到已知的DP模型上。如果能映射到背包、LCS、最短路径这些经典模型，直接套用对应框架；如果不能，就从状态定义开始推演。

推导阶段控制在5到10分钟。先在草稿纸上写出状态定义和转移方程，再用一个小例子手动验证一遍。这一步特别关键——你会发现很多问题在手动推导时就能暴露出来，比如状态定义缺少某个维度、边界条件没考虑全。等手推结果验证无误后，再开始写代码。

编码阶段控制在10到15分钟。按照状态定义、初始化、转移循环、返回值的顺序依次实现。代码风格要清晰，变量命名要有语义，不要为了省事写成dp、dp1、dp2这种难以区分的名字。笔试环境里的编辑器没有自动补全也没有代码检查，写的时候就要格外仔细。

提示：如果你在笔试时发现时间不够，优先保证暴力解能通过小规模测试用例。很多公司的笔试判分规则是部分用例给部分分数，不要因为追求完美解法而放弃基础分。

还有一个小建议：面试时如果被问到动态规划题，一定要把思考过程讲出来。面试官想看到的不是你直接写出正确答案，而是你如何从题目出发，一步步推导出状态和转移方程。哪怕最终代码有小瑕疵，只要思路清晰，分数也不会低。你可以先说“我倾向于用一维DP”，然后解释为什么可以压成一维，最后再写出代码——这个过程本身就在展示你的工程思维。

拿到一道题先想清楚再动手，动态规划没有想象的那么神秘，它本质上是把暴力枚举的所有可能解空间，用一张表组织起来，去掉了重复计算。能把这张表画明白，题目就解了一半。