罗罗编程学习记录
本页内容 展开查看

02.7.1.1 DP 状态设计与转移

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.1 DP 基础与线性 DP

02.7.1.1-001 动态规划适用的三个条件是什么?

一句话结论

DP 适用于满足最优子结构、无后效性、重叠子问题的问题:最优解可由子问题最优解组成,当前状态决策不影响未来状态,相同状态被重复求解;三者缺一需换贪心/回溯等方法。

概念解释

  • 最优子结构:子问题最优可拼出全局最优。
  • 无后效性:状态一旦确定,后续不再受之前路径影响。
  • 重叠子问题:相同状态反复出现。

原理流程

  1. 检查最优解能否分解到子问题。
  2. 确认未来只依赖当前状态。
  3. 识别重复状态决定 DP/记忆化价值。

代码 / 图示

原问题最优 = 合并各子问题最优
状态确定后,历史路径不再参与后续决策

常见误区

  • 误区:有重叠子问题就一定 DP;正解:还需最优子结构,计数/可行性也可 DP。
  • 误区:DP 要求求最值;正解:计数、可行性判断同样适用。

追问

  • Q:不满足无后效性怎么办? A:补充状态维度记录必要历史,或改回溯。
  • Q:最优子结构怎么验证? A:反证某子问题非最优时全局不可能最优。

02.7.1.1-002 DP 解题五步法是什么?

一句话结论

五步:定义状态、写转移方程、定初始化与边界、定遍历顺序、取结果并做空间优化;先把“最后一步”想清楚,再逐层落到数组。

概念解释

  • 状态:dp[i] 或 dp[i][j] 的含义。
  • 转移:旧状态如何推出新状态。
  • 顺序:依赖状态先算。

原理流程

  1. 定义状态表示什么。
  2. 枚举最后一步决策写方程。
  3. 初始化边界,按依赖顺序填表。
  4. 取目标状态,评估滚动优化。

代码 / 示例

状态定义 → 转移方程 → 初始化 → 遍历顺序 → 结果与优化

常见误区

  • 误区:先写代码再补状态含义;正解:状态定义先行,代码只是填表。
  • 误区:遍历顺序与依赖矛盾;正解:被依赖状态先计算。

追问

  • Q:五步法哪步最关键? A:状态定义,定义错后面全偏。
  • Q:空间优化在哪步考虑? A:最后一步,看依赖是否只保留近层。

02.7.1.1-003 状态定义有哪三种常见角度?

一句话结论

三种:前 i 个元素的结果(前缀视角)、以 i 结尾的结果(后缀/端点视角)、容量/数值为 j 的结果(背包视角);定义角度决定转移方向与最终取哪个状态。

概念解释

  • 前缀:dp[i] 前 i 个。
  • 结尾:dp[i] 必须以 i 收尾。
  • 容量:dp[j] 约束为 j。

原理流程

  1. 明确答案对应前缀、结尾还是容量。
  2. 按角度命名状态。
  3. 转移与返回状态匹配定义。

代码 / 示例

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 怎么从“最后一步”反推转移方程?

一句话结论

思考最优解的最后一个决策是什么(选/不选、从哪个前驱来),把最后一步的选择枚举出来,对应到旧状态的几种取值,取最值或求和即转移方程。

概念解释

  • 最后一步:构成答案的末尾决策。
  • 前驱:到达当前状态前的状态。

原理流程

  1. 写出答案的最后一步可能形态。
  2. 对应前驱状态。
  3. 合并各前驱得方程。

代码 / 示例

打家劫舍最后一步:偷 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 转移),每类对应一个前驱状态;决策之间互斥且穷尽,方程对各类取最值或求和。

概念解释

  • 决策分类:末步的不同选择。
  • 互斥穷尽:覆盖所有合法情况。

原理流程

  1. 列末步所有可能选择。
  2. 每类映射前驱状态。
  3. 合并成方程。

代码 / 示例

编辑距离末步:相等 → 对角;不等 → 替换/删除/插入三前驱取 min

常见误区

  • 误区:决策有遗漏;正解:对照小规模例子补齐分支。
  • 误区:不同决策重复计入;正解:分类互斥避免重复。

追问

  • Q:背包选/不选是哪类? A:01 背包两个决策分支。
  • Q:求和类方程怎么合并? A:各前驱方案数相加。

02.7.1.1-006 初始化与边界条件怎么定?

一句话结论

初始化填递推无法推出的基准状态:空前缀、容量 0、空串;最值问题按题意填 0 或 -INF,计数问题 dp[0]=1;边界要与状态定义一致,避免首项漏算。

概念解释

  • 基准:最小规模状态。
  • 哨兵:-INF 表示不可达。

原理流程

  1. 找递推起点(空/零)。
  2. 按最值/计数填初值。
  3. 检查首项能否被方程推出。

代码 / 示例

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 倒序防重复使用;二维区间按长度外层、对角线方向;保证填表时前驱已就绪。

概念解释

  • 依赖:方程引用的旧状态。
  • 顺序:前驱先于当前。

原理流程

  1. 列出方程引用哪些旧状态。
  2. 安排循环方向。
  3. 核对填表顺序无未定义引用。

代码 / 示例

线性:i 从小到大;01 背包:j 从大到小;区间:len 从小到大

常见误区

  • 误区:所有 DP 都正序;正解:01 背包必须倒序。
  • 误区:区间 DP 按 i 正序;正解:按区间长度外层枚举。

追问

  • Q:完全背包为什么正序? A:允许重复使用,同物品可再次转移。
  • Q:怎么检查顺序错误? A:看引用状态是否已填。

02.7.1.1-008 最终结果取哪个状态?

一句话结论

前缀视角取最后一个状态;结尾视角需遍历所有结尾取最值;容量视角取目标容量;计数类取目标状态;先回到状态定义确认答案对应哪个 dp 值。

概念解释

  • 前缀:全局答案在末态。
  • 结尾:答案分散在各结尾。

原理流程

  1. 对照状态定义。
  2. 前缀取末态,结尾扫最大。
  3. 容量取目标 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 滚动数组怎么做空间优化?

一句话结论

若转移只依赖前一层或前几个位置,用变量/一维数组保留所需旧状态,覆盖无关历史;一维背包直接压到容量维;优化时注意倒序/正序防止覆盖未用旧值。

概念解释

  • 依赖近层:不需保留全表。
  • 滚动:旧层覆盖复用。

原理流程

  1. 分析方程依赖哪些旧状态。
  2. 用变量或一维数组承接。
  3. 调整顺序避免覆盖。

代码 / 示例

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:状态枚举 + 最优子结构。
  • 回溯:方案枚举。

原理流程

  1. 看子问题是否独立。
  2. 看是否需保留多状态。
  3. 对比各方法适用条件。

代码 / 图示

贪心:一步一抉择;DP:填表;回溯:决策树枚举;分治:切分合并

常见误区

  • 误区:能 DP 的题贪心一定对;正解:贪心需局部最优等价全局,DP 更稳。
  • 误区:DP 与回溯互斥;正解:记忆化搜索是二者桥梁。

追问

  • Q:DP 比贪心多保留什么? A:各状态最优值,不丢弃备选。
  • Q:分治子问题重叠吗? A:分治通常独立,重叠才转 DP。

02.7.1.1-011 状态维度过多怎么压缩?

一句话结论

先列必要状态维度,去掉被其他维度推出的冗余项;可用位掩码、滚动层、对偶转换减少维度;若状态空间随 n 指数膨胀,需评估题目规模是否还适合 DP。

概念解释

  • 冗余维度:可由其他状态推导。
  • 压缩:掩码/滚动/换维。

原理流程

  1. 列全影响结果的维度。
  2. 剔除冗余。
  3. 评估剩余状态空间。

代码 / 示例

股票:天数 × 持股状态;去掉可推导的价格维度

常见误区

  • 误区:盲目加维度保安全;正解:冗余维度增大状态空间。
  • 误区:压缩后丢失必要历史;正解:先确认该维度可推。

追问

  • Q:状态空间多大不可行? A:指数级且 n 较大时需换思路。
  • Q:位掩码压缩适用什么? A:集合类状态,n 较小。

02.7.1.1-012 怎么理解无后效性?

一句话结论

无后效性指一旦状态确定,后续决策只看当前状态,不关心如何到达它;若后续选择依赖完整历史路径,当前状态定义不足,需补充历史维度或改用回溯。

概念解释

  • 状态充分:未来由当前状态决定。
  • 历史无关:到达路径不影响后续。

原理流程

  1. 检查后续决策依赖哪些信息。
  2. 这些信息是否都在状态里。
  3. 不足则补维度。

代码 / 示例

背包:剩余容量足够决定后续;排列:历史顺序影响后续,状态不足

常见误区

  • 误区:把路径序列当状态;正解:路径过长时 DP 不可行。
  • 误区:认为加了状态就无后效;正解:状态必须覆盖所有历史影响。

追问

  • Q:股票状态为什么要记持股与否? A:后续买卖依赖当前持有状态。
  • Q:无后效性违反怎么办? A:补状态维度或回溯枚举。

02.7.1.1-013 重叠子问题与记忆化怎么呼应?

一句话结论

DP 表每个状态只算一次,本质是缓存重叠子问题;自顶向下记忆化先算需要的状态,自底向上填满全表;两者状态与转移一致,重叠越多记忆化收益越大。

概念解释

  • 重叠:同状态多次出现。
  • 缓存:memo / dp 表。

原理流程

  1. 识别重复状态。
  2. 递归 memo 或填表复用。
  3. 避免重复计算。

代码 / 示例

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。

原理流程

  1. 定义 dp[i]。
  2. 方程 dp[i]=dp[i-1]+dp[i-2]。
  3. 初始化边界,顺序填表。

代码 / 示例

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)。

概念解释

  • 约束:相邻不能同时偷。
  • 末步:偷/不偷。

原理流程

  1. 定义前缀最优金额。
  2. 方程取两种末步最大。
  3. 初始化两家边界。

代码 / 示例

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]。
  • 接续/重起:两种末步。

原理流程

  1. 定义结尾状态。
  2. 方程 max(dp[i-1]+a[i], a[i])。
  3. 全局维护最大值。

代码 / 示例

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 结尾值。

原理流程

  1. 同时记结尾最大、最小。
  2. 新 max/min 由旧 max、旧 min、a[i] 比较。
  3. 全局取最大。

代码 / 示例

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 结果怎么还原具体方案?

一句话结论

填表时记录每个状态的前驱选择(决策来源),结束后从目标状态沿前驱指针回溯到起点,反向得到方案;只需求最值/计数可不记录前驱。

概念解释

  • 前驱记录:每步从哪来。
  • 回溯还原:目标 → 起点。

原理流程

  1. 填表时存选择来源。
  2. 终态沿前驱回推。
  3. 反转得方案顺序。

代码 / 示例

prev[i] = j;从 ans 状态按 prev 回链,反转输出

常见误区

  • 误区:只存最值不存前驱;正解:要方案必须额外记录来源。
  • 误区:前驱指针覆盖多个最优来源;正解:按题意存其一或全部。

追问

  • Q:还原 LIS 方案怎么做? A:记录每个 dp[i] 的前驱 j。
  • Q:记录前驱增加多少空间? A:O(n) 前驱数组。

02.7.1.1-019 状态定义常见错误有哪些?

一句话结论

高频错误:前缀与结尾混用、状态含义与返回值不符、漏掉必要历史维度、初始化与定义矛盾、转移前驱列不全;回到五步法逐项核对状态含义与方程。

概念解释

  • 定义一致性:状态、转移、返回对齐。
  • 维度完整:覆盖历史影响。

原理流程

  1. 重读状态定义。
  2. 核对方程前驱。
  3. 检查初始化与返回状态。

代码 / 示例

排查:前缀/结尾 / 维度 / 初始化 / 前驱枚举 / 返回取值

常见误区

  • 误区:状态名随意写;正解:明确“前 i”还是“以 i 结尾”。
  • 误区:二维状态漏一维;正解:列出所有决策约束。

追问

  • Q:结果与手算不符先查什么? A:状态定义与初始化。
  • Q:转移重复计入怎么查? A:核对决策分类是否互斥。

02.7.1.1-020 DP 复杂度口径怎么报?

一句话结论

时间 = 状态数 × 单状态转移代价;空间 = 状态表大小,滚动优化后按保留层数;先数状态维度值域,再看每状态枚举多少前驱;报清平均/最坏口径。

概念解释

  • 状态数:各维度值域乘积。
  • 转移代价:内层枚举分支数。

原理流程

  1. 数状态空间。
  2. 乘单状态转移代价。
  3. 空间按表大小或滚动层。

代码 / 示例

二维 DP:O(mn) 状态 × O(1) 转移 → O(mn)
背包:O(nW)

常见误区

  • 误区:只报数组大小不报转移;正解:内层循环分支要计入时间。
  • 误区:优化后空间与时间混谈;正解:空间随滚动下降,时间不变。

追问

  • Q:区间 DP 状态数? A:O(n²),转移枚举 k → O(n³)。
  • Q:记忆化复杂度怎么报? A:可达状态数 × 单状态代价。