什么是动态规划？｜腾讯客户端面经解析

60 秒回答模板

可以这样回答：动态规划适合具有最优子结构和重叠子问题的问题。回答时要讲清状态定义、转移方程、初始化、遍历顺序和结果位置，而不是先展开 DP 与贪心对比。先定义 dp[i] 或 dp[i][j] 表示什么，再从更小子问题推到当前状态；初始化边界状态；按依赖方向遍历；必要时用滚动数组做空间压缩。 DP 比暴力枚举少重复计算，但状态设计可能带来较高时间和空间成本。能否用贪心要另行证明贪心选择性质，不能默认替代 DP。要避免状态含义不清、转移漏来源、初始化错误、遍历顺序反了和空间压缩覆盖旧状态。验证时重点看：用小样例手推状态表、检查边界、验证复杂度、和暴力结果对拍。

考点 考点边界

主线 核心机制

易错点 把“什么是动态规划”主要讲成 DP vs 贪心，漏掉状…

深入解析

考点边界

这题必须围绕“动态规划定义与解题框架”本身回答，不能套相邻大类模板。先给定义或目标，再展开机制、边界、取舍和验证抓手。回答时要主动点出题面关键词对应的对象、输入输出和约束条件，避免把具体问题讲成宽泛复习提纲。本题对应“动态规划定义与解题框架”，核心前提是：动态规划适合具有最优子结构和重叠子问题的问题。回答时要讲清状态定义、转移方程、初始化、遍历顺序和结果位置，而不是先展开 DP 与贪心对比。

核心机制

先定义 dp[i] 或 dp[i][j] 表示什么，再从更小子问题推到当前状态；初始化边界状态；按依赖方向遍历；必要时用滚动数组做空间压缩。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

DP 比暴力枚举少重复计算，但状态设计可能带来较高时间和空间成本。能否用贪心要另行证明贪心选择性质，不能默认替代 DP。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

要避免状态含义不清、转移漏来源、初始化错误、遍历顺序反了和空间压缩覆盖旧状态。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：用小样例手推状态表、检查边界、验证复杂度、和暴力结果对拍。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

把“什么是动态规划”主要讲成 DP vs 贪心，漏掉状态、转移、初始化和遍历顺序。
只背最优子结构/重叠子问题，不会用小样例手推状态表。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

设计 DP 时第一步最重要的是什么？

定义状态含义，明确 dp 数组每个下标代表的子问题，否则转移方程和遍历顺序都无法可靠推出。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

什么时候可以把 DP 优化成滚动数组？

当当前状态只依赖有限个上一层或相邻状态时，可以压缩空间，但要注意遍历方向不能覆盖还需要的旧值。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

“什么是动态规划”继续追问时最该补哪条边界？

应该围绕“动态规划定义与解题框架”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。

“什么是动态规划”怎样回答才不是只背概念？

看它能否把“动态规划定义与解题框架”的机制链路、关键取舍和可观测信号连起来。回答时应落到具体状态变化、数据路径、复杂度、指标或排查工具，而不是只复述定义。

“什么是动态规划”怎么判断算法选型？

先看是否有最优子结构、单调性、局部选择是否会影响全局最优，以及数据结构能否降低查找或更新成本。动态规划、贪心、二分、哈希、堆和树结构分别对应不同的不变量。