02.7.1.1 DP 状态设计与转移
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP
02.7.1.1-001 动态规划适用的三个条件是什么?
一句话结论
DP 适用于满足最优子结构、无后效性、重叠子问题的问题:最优解可由子问题最优解组成,当前状态决策不影响未来状态,相同状态被重复求解;三者缺一需换贪心/回溯等方法。
概念解释
- 最优子结构:子问题最优可拼出全局最优。
- 无后效性:状态一旦确定,后续不再受之前路径影响。
- 重叠子问题:相同状态反复出现。
原理流程
- 检查最优解能否分解到子问题。
- 确认未来只依赖当前状态。
- 识别重复状态决定 DP/记忆化价值。
代码 / 图示
原问题最优 = 合并各子问题最优
状态确定后,历史路径不再参与后续决策
常见误区
- 误区:有重叠子问题就一定 DP;正解:还需最优子结构,计数/可行性也可 DP。
- 误区:DP 要求求最值;正解:计数、可行性判断同样适用。
追问
- Q:不满足无后效性怎么办? A:补充状态维度记录必要历史,或改回溯。
- Q:最优子结构怎么验证? A:反证某子问题非最优时全局不可能最优。
02.7.1.1-002 DP 解题五步法是什么?
一句话结论
五步:定义状态、写转移方程、定初始化与边界、定遍历顺序、取结果并做空间优化;先把“最后一步”想清楚,再逐层落到数组。
概念解释
- 状态:dp[i] 或 dp[i][j] 的含义。
- 转移:旧状态如何推出新状态。
- 顺序:依赖状态先算。
原理流程
- 定义状态表示什么。
- 枚举最后一步决策写方程。
- 初始化边界,按依赖顺序填表。
- 取目标状态,评估滚动优化。
代码 / 示例
状态定义 → 转移方程 → 初始化 → 遍历顺序 → 结果与优化
常见误区
- 误区:先写代码再补状态含义;正解:状态定义先行,代码只是填表。
- 误区:遍历顺序与依赖矛盾;正解:被依赖状态先计算。
追问
- Q:五步法哪步最关键? A:状态定义,定义错后面全偏。
- Q:空间优化在哪步考虑? A:最后一步,看依赖是否只保留近层。
02.7.1.1-003 状态定义有哪三种常见角度?
一句话结论
三种:前 i 个元素的结果(前缀视角)、以 i 结尾的结果(后缀/端点视角)、容量/数值为 j 的结果(背包视角);定义角度决定转移方向与最终取哪个状态。
概念解释
- 前缀:dp[i] 前 i 个。
- 结尾:dp[i] 必须以 i 收尾。
- 容量:dp[j] 约束为 j。
原理流程
- 明确答案对应前缀、结尾还是容量。
- 按角度命名状态。
- 转移与返回状态匹配定义。
代码 / 示例
dp[i]:前 i 个最大和
dp[i]:以 i 结尾的最长子序列
dp[j]:容量 j 的最大价值
常见误区
- 误区:前缀与结尾混用;正解:前缀可不含 i,结尾必须含 i。
- 误区:返回状态选错;正解:结尾视角要遍历取 max,前缀视角直接取末态。
追问
- Q:最大子数组和用哪种? A:以 i 结尾 dp[i],再全局取 max。
- Q:背包用哪种? A:容量 j 视角。
02.7.1.1-004 怎么从“最后一步”反推转移方程?
一句话结论
思考最优解的最后一个决策是什么(选/不选、从哪个前驱来),把最后一步的选择枚举出来,对应到旧状态的几种取值,取最值或求和即转移方程。
概念解释
- 最后一步:构成答案的末尾决策。
- 前驱:到达当前状态前的状态。
原理流程
- 写出答案的最后一步可能形态。
- 对应前驱状态。
- 合并各前驱得方程。
代码 / 示例
打家劫舍最后一步:偷 i → dp[i-2]+a[i];不偷 → dp[i-1]
dp[i] = max(dp[i-1], dp[i-2]+a[i])
常见误区
- 误区:跳过最后一步直接套模板;正解:先枚举末步选择再写方程。
- 误区:转移漏掉一种前驱;正解:把末步所有合法情况列全。
追问
- Q:最后一步找不到怎么办? A:换状态定义或画小规模例子对照。
- Q:转移方程里加什么? A:按题意取 max/min 或累加计数。
02.7.1.1-005 转移方程怎么枚举决策?
一句话结论
按最后一步的选择分类(选当前/不选、匹配/不匹配、从 j 转移),每类对应一个前驱状态;决策之间互斥且穷尽,方程对各类取最值或求和。
概念解释
- 决策分类:末步的不同选择。
- 互斥穷尽:覆盖所有合法情况。
原理流程
- 列末步所有可能选择。
- 每类映射前驱状态。
- 合并成方程。
代码 / 示例
编辑距离末步:相等 → 对角;不等 → 替换/删除/插入三前驱取 min
常见误区
- 误区:决策有遗漏;正解:对照小规模例子补齐分支。
- 误区:不同决策重复计入;正解:分类互斥避免重复。
追问
- Q:背包选/不选是哪类? A:01 背包两个决策分支。
- Q:求和类方程怎么合并? A:各前驱方案数相加。
02.7.1.1-006 初始化与边界条件怎么定?
一句话结论
初始化填递推无法推出的基准状态:空前缀、容量 0、空串;最值问题按题意填 0 或 -INF,计数问题 dp[0]=1;边界要与状态定义一致,避免首项漏算。
概念解释
- 基准:最小规模状态。
- 哨兵:-INF 表示不可达。
原理流程
- 找递推起点(空/零)。
- 按最值/计数填初值。
- 检查首项能否被方程推出。
代码 / 示例
int[] dp = new int[n + 1];
dp[0] = 1; // 计数基准
// 最值不可达:dp[j] = -INF; dp[0] = 0;
常见误区
- 误区:最值问题全初始 0;正解:要求恰好装满时不可达要 -INF。
- 误区:dp[0] 与状态定义不符;正解:空集合/空容量按题意定义。
追问
- Q:二维 DP 第一行第一列怎么填? A:按空串/空前缀含义递推边界。
- Q:初始化错了表现是什么? A:首项结果偏差或不可达状态被当合法。
02.7.1.1-007 遍历顺序怎么确定?
一句话结论
按状态依赖关系排序:被依赖的前驱状态先算;一维通常从前到后,背包 01 倒序防重复使用;二维区间按长度外层、对角线方向;保证填表时前驱已就绪。
概念解释
- 依赖:方程引用的旧状态。
- 顺序:前驱先于当前。
原理流程
- 列出方程引用哪些旧状态。
- 安排循环方向。
- 核对填表顺序无未定义引用。
代码 / 示例
线性:i 从小到大;01 背包:j 从大到小;区间:len 从小到大
常见误区
- 误区:所有 DP 都正序;正解:01 背包必须倒序。
- 误区:区间 DP 按 i 正序;正解:按区间长度外层枚举。
追问
- Q:完全背包为什么正序? A:允许重复使用,同物品可再次转移。
- Q:怎么检查顺序错误? A:看引用状态是否已填。
02.7.1.1-008 最终结果取哪个状态?
一句话结论
前缀视角取最后一个状态;结尾视角需遍历所有结尾取最值;容量视角取目标容量;计数类取目标状态;先回到状态定义确认答案对应哪个 dp 值。
概念解释
- 前缀:全局答案在末态。
- 结尾:答案分散在各结尾。
原理流程
- 对照状态定义。
- 前缀取末态,结尾扫最大。
- 容量取目标 j。
代码 / 示例
int ans = 0;
for (int x : dp) ans = Math.max(ans, x); // 结尾视角
常见误区
- 误区:结尾视角直接返回 dp[n-1];正解:最优结尾不一定在末尾。
- 误区:计数与最值返回混淆;正解:计数累加,最值比较。
追问
- Q:LIS 返回哪个? A:遍历 dp 取最大,结尾视角。
- Q:背包返回哪个? A:dp[W] 目标容量。
02.7.1.1-009 滚动数组怎么做空间优化?
一句话结论
若转移只依赖前一层或前几个位置,用变量/一维数组保留所需旧状态,覆盖无关历史;一维背包直接压到容量维;优化时注意倒序/正序防止覆盖未用旧值。
概念解释
- 依赖近层:不需保留全表。
- 滚动:旧层覆盖复用。
原理流程
- 分析方程依赖哪些旧状态。
- 用变量或一维数组承接。
- 调整顺序避免覆盖。
代码 / 示例
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1; prev1 = cur;
}
常见误区
- 误区:优化后顺序不变导致覆盖;正解:依赖当前层旧值时注意倒序。
- 误区:多依赖硬压成单变量;正解:保留所需多个旧值。
追问
- Q:二维 DP 能压到几维? A:看依赖,常压到一维或两变量。
- Q:空间优化影响时间吗? A:不改变转移次数,只减空间。
02.7.1.1-010 DP、贪心、回溯、分治怎么对比?
一句话结论
贪心每步局部最优不回头,DP 枚举所有状态保留最优,回溯枚举完整方案,分治独立子问题合并;DP 靠状态表去重,回溯不合并子问题;按是否需要枚举状态与子结构关系选择。
概念解释
- 贪心:局部最优推导全局。
- DP:状态枚举 + 最优子结构。
- 回溯:方案枚举。
原理流程
- 看子问题是否独立。
- 看是否需保留多状态。
- 对比各方法适用条件。
代码 / 图示
贪心:一步一抉择;DP:填表;回溯:决策树枚举;分治:切分合并
常见误区
- 误区:能 DP 的题贪心一定对;正解:贪心需局部最优等价全局,DP 更稳。
- 误区:DP 与回溯互斥;正解:记忆化搜索是二者桥梁。
追问
- Q:DP 比贪心多保留什么? A:各状态最优值,不丢弃备选。
- Q:分治子问题重叠吗? A:分治通常独立,重叠才转 DP。
02.7.1.1-011 状态维度过多怎么压缩?
一句话结论
先列必要状态维度,去掉被其他维度推出的冗余项;可用位掩码、滚动层、对偶转换减少维度;若状态空间随 n 指数膨胀,需评估题目规模是否还适合 DP。
概念解释
- 冗余维度:可由其他状态推导。
- 压缩:掩码/滚动/换维。
原理流程
- 列全影响结果的维度。
- 剔除冗余。
- 评估剩余状态空间。
代码 / 示例
股票:天数 × 持股状态;去掉可推导的价格维度
常见误区
- 误区:盲目加维度保安全;正解:冗余维度增大状态空间。
- 误区:压缩后丢失必要历史;正解:先确认该维度可推。
追问
- Q:状态空间多大不可行? A:指数级且 n 较大时需换思路。
- Q:位掩码压缩适用什么? A:集合类状态,n 较小。
02.7.1.1-012 怎么理解无后效性?
一句话结论
无后效性指一旦状态确定,后续决策只看当前状态,不关心如何到达它;若后续选择依赖完整历史路径,当前状态定义不足,需补充历史维度或改用回溯。
概念解释
- 状态充分:未来由当前状态决定。
- 历史无关:到达路径不影响后续。
原理流程
- 检查后续决策依赖哪些信息。
- 这些信息是否都在状态里。
- 不足则补维度。
代码 / 示例
背包:剩余容量足够决定后续;排列:历史顺序影响后续,状态不足
常见误区
- 误区:把路径序列当状态;正解:路径过长时 DP 不可行。
- 误区:认为加了状态就无后效;正解:状态必须覆盖所有历史影响。
追问
- Q:股票状态为什么要记持股与否? A:后续买卖依赖当前持有状态。
- Q:无后效性违反怎么办? A:补状态维度或回溯枚举。
02.7.1.1-013 重叠子问题与记忆化怎么呼应?
一句话结论
DP 表每个状态只算一次,本质是缓存重叠子问题;自顶向下记忆化先算需要的状态,自底向上填满全表;两者状态与转移一致,重叠越多记忆化收益越大。
概念解释
- 重叠:同状态多次出现。
- 缓存:memo / dp 表。
原理流程
- 识别重复状态。
- 递归 memo 或填表复用。
- 避免重复计算。
代码 / 示例
fib:朴素 O(2ⁿ);memo/dp O(n)
常见误区
- 误区:DP 消除了分治重复;正解:DP 用表记录结果复用。
- 误区:无重叠也强行 DP;正解:状态不重复时分治/递归即可。
追问
- Q:记忆化与 DP 哪个先写? A:递归思路清晰后可加 memo,再转填表。
- Q:重叠程度怎么看? A:递归树重复子树越多收益越大。
02.7.1.1-014 爬楼梯(LC 70)DP 怎么推?
一句话结论
状态 dp[i] 爬到第 i 阶方法数;最后一步跨 1 阶来自 dp[i-1],跨 2 阶来自 dp[i-2];初始化 dp[0]=1、dp[1]=1;从前到后遍历;时间 O(n),空间可压 O(1)。
概念解释
- 状态:到第 i 阶的方法数。
- 转移:末步跨 1 或 2。
原理流程
- 定义 dp[i]。
- 方程 dp[i]=dp[i-1]+dp[i-2]。
- 初始化边界,顺序填表。
代码 / 示例
int climb(int n) {
int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b; a = b; b = c;
}
return b;
}
常见误区
- 误区:dp[0] 初始 0;正解:平地到 0 阶一种方法。
- 误区:n=1 返回 dp[2];正解:边界单独覆盖。
追问
- Q:跨 m 阶怎么改? A:方程累加 dp[i-1..m]。
- Q:复杂度? A:时间 O(n),空间 O(1)。
02.7.1.1-015 打家劫舍(LC 198)DP 怎么推?
一句话结论
dp[i] 前 i 家最高金额;末步偷第 i 家则前一家不能偷,取 dp[i-2]+nums[i];不偷取 dp[i-1];初始化 dp[0]=0、dp[1]=nums[0];正序遍历;时间 O(n),空间 O(1)。
概念解释
- 约束:相邻不能同时偷。
- 末步:偷/不偷。
原理流程
- 定义前缀最优金额。
- 方程取两种末步最大。
- 初始化两家边界。
代码 / 示例
int rob(int[] a) {
int prev2 = 0, prev1 = 0;
for (int x : a) {
int cur = Math.max(prev1, prev2 + x);
prev2 = prev1; prev1 = cur;
}
return prev1;
}
常见误区
- 误区:偷 i 还能偷 i-1;正解:相邻互斥。
- 误区:状态定义成以 i 结尾;正解:前缀视角更自然。
追问
- Q:环形街区怎么改? A:拆成两种线性情况取最大(见 02.7.1.4)。
- Q:复杂度? A:O(n) 时间,O(1) 空间。
02.7.1.1-016 最大子数组和(LC 53)DP 怎么推?
一句话结论
dp[i] 以 i 结尾的最大连续子数组和;末步接续前面 dp[i-1]+a[i] 或从 i 重起 a[i];初始化 dp[0]=a[0];正序;全局取最大;时间 O(n),空间 O(1)。
概念解释
- 结尾视角:必须含 a[i]。
- 接续/重起:两种末步。
原理流程
- 定义结尾状态。
- 方程 max(dp[i-1]+a[i], a[i])。
- 全局维护最大值。
代码 / 示例
int cur = a[0], ans = a[0];
for (int i = 1; i < a.length; i++) {
cur = Math.max(a[i], cur + a[i]);
ans = Math.max(ans, cur);
}
常见误区
- 误区:前缀视角直接累加;正解:负数前缀应截断重起。
- 误区:全局最大漏更新;正解:每个结尾都要参与比较。
追问
- Q:全负数返回什么? A:最大单元素,不是 0。
- Q:空间优化后变量含义? A:当前结尾最大和。
02.7.1.1-017 乘积最大子数组(LC 152)为什么要双状态?
一句话结论
乘法负负得正,最小值乘负数可变最大;同时维护以 i 结尾的最大乘积与最小乘积,转移时三者(含 a[i])比较;初始化两者为 a[0];正序;时间 O(n),空间 O(1)。
概念解释
- 符号翻转:最小乘积可能翻成最大。
- 双状态:max 与 min 结尾值。
原理流程
- 同时记结尾最大、最小。
- 新 max/min 由旧 max、旧 min、a[i] 比较。
- 全局取最大。
代码 / 示例
int maxP = a[0], minP = a[0], ans = a[0];
for (int i = 1; i < a.length; i++) {
int x = a[i];
int tMax = Math.max(x, Math.max(maxP * x, minP * x));
int tMin = Math.min(x, Math.min(maxP * x, minP * x));
maxP = tMax; minP = tMin;
ans = Math.max(ans, maxP);
}
常见误区
- 误区:只维护最大乘积;正解:负数最小值必须保留。
- 误区:更新 max 后再算 min 用了新值;正解:先用旧值算完再覆盖。
追问
- Q:含 0 怎么处理? A:0 截断两侧,乘积自然归零重起。
- Q:复杂度? A:O(n) 时间 O(1) 空间。
02.7.1.1-018 DP 结果怎么还原具体方案?
一句话结论
填表时记录每个状态的前驱选择(决策来源),结束后从目标状态沿前驱指针回溯到起点,反向得到方案;只需求最值/计数可不记录前驱。
概念解释
- 前驱记录:每步从哪来。
- 回溯还原:目标 → 起点。
原理流程
- 填表时存选择来源。
- 终态沿前驱回推。
- 反转得方案顺序。
代码 / 示例
prev[i] = j;从 ans 状态按 prev 回链,反转输出
常见误区
- 误区:只存最值不存前驱;正解:要方案必须额外记录来源。
- 误区:前驱指针覆盖多个最优来源;正解:按题意存其一或全部。
追问
- Q:还原 LIS 方案怎么做? A:记录每个 dp[i] 的前驱 j。
- Q:记录前驱增加多少空间? A:O(n) 前驱数组。
02.7.1.1-019 状态定义常见错误有哪些?
一句话结论
高频错误:前缀与结尾混用、状态含义与返回值不符、漏掉必要历史维度、初始化与定义矛盾、转移前驱列不全;回到五步法逐项核对状态含义与方程。
概念解释
- 定义一致性:状态、转移、返回对齐。
- 维度完整:覆盖历史影响。
原理流程
- 重读状态定义。
- 核对方程前驱。
- 检查初始化与返回状态。
代码 / 示例
排查:前缀/结尾 / 维度 / 初始化 / 前驱枚举 / 返回取值
常见误区
- 误区:状态名随意写;正解:明确“前 i”还是“以 i 结尾”。
- 误区:二维状态漏一维;正解:列出所有决策约束。
追问
- Q:结果与手算不符先查什么? A:状态定义与初始化。
- Q:转移重复计入怎么查? A:核对决策分类是否互斥。
02.7.1.1-020 DP 复杂度口径怎么报?
一句话结论
时间 = 状态数 × 单状态转移代价;空间 = 状态表大小,滚动优化后按保留层数;先数状态维度值域,再看每状态枚举多少前驱;报清平均/最坏口径。
概念解释
- 状态数:各维度值域乘积。
- 转移代价:内层枚举分支数。
原理流程
- 数状态空间。
- 乘单状态转移代价。
- 空间按表大小或滚动层。
代码 / 示例
二维 DP:O(mn) 状态 × O(1) 转移 → O(mn)
背包:O(nW)
常见误区
- 误区:只报数组大小不报转移;正解:内层循环分支要计入时间。
- 误区:优化后空间与时间混谈;正解:空间随滚动下降,时间不变。
追问
- Q:区间 DP 状态数? A:O(n²),转移枚举 k → O(n³)。
- Q:记忆化复杂度怎么报? A:可达状态数 × 单状态代价。