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

02.7.2.1 区间 DP

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.7 动态规划 / 02.7.2 区间树形与状态压缩 DP

02.7.2.1-001 区间 DP 的状态怎么定义?

一句话结论

区间 DP 状态 dp[i][j] 表示子区间 [i,j] 上的最优值/方案数;答案通常在 dp[0][n-1];转移枚举分割点 k,把区间拆成 [i,k] 与 [k+1,j] 合并。

概念解释

  • 区间状态:两端点界定子问题。
  • 分割点:合并位置。

原理流程

  1. 定义区间含义。
  2. 枚举 k 合并左右子区间。
  3. 取全局区间结果。

代码 / 示例

dp[i][j] = opt(dp[i][k] + dp[k+1][j] + cost(i,j,k))

常见误区

  • 误区:状态定义成前缀;正解:区间问题需两端点。
  • 误区:分割点漏掉边界;正解:k 从 i 到 j-1。

追问

  • Q:答案在哪个状态? A:完整区间 dp[0][n-1]。
  • Q:区间 DP 状态数? A:O(n²)。

02.7.2.1-002 区间枚举顺序为什么按长度外层?

一句话结论

区间转移依赖更短的左右子区间,必须先算所有短区间再算长区间;外层循环区间长度,内层枚举起点 i,终点 j=i+len-1,保证子区间已填表。

概念解释

  • 依赖:更短区间。
  • 长度外层:短先于长。

原理流程

  1. len 从 1 到 n。
  2. 枚举起点 i。
  3. j=i+len-1 填表。

代码 / 示例

for (int len = 1; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        ...
    }

常见误区

  • 误区:按 i 正序填;正解:子区间可能在右侧,i 正序未就绪。
  • 误区:len 从 2 起漏单元素初始化;正解:先填 len=1 基准。

追问

  • Q:记忆化写法顺序还重要吗? A:递归按需计算,天然先算子区间。
  • Q:长度从几开始? A:单元素基准 len=1。

02.7.2.1-003 转移怎么枚举分割点 k?

一句话结论

在 [i,j] 内枚举 k∈[i,j-1],左区间 [i,k]、右区间 [k+1,j];按题意取最值或累加方案;分割点代价(合并成本、两端值)按题加入方程。

概念解释

  • 分割:最后合并位置。
  • 代价:合并该区间的成本。

原理流程

  1. 列 k 范围。
  2. 左右子区间取值。
  3. 加合并代价取最优。

代码 / 示例

for (int k = i; k < j; k++)
    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);

常见误区

  • 误区:k 取到 j;正解:右区间非空,k<j。
  • 误区:漏加合并代价;正解:区间合并成本要计入。

追问

  • Q:分割点枚举代价? A:O(n) 每区间,总 O(n³)。
  • Q:无分割代价的题? A:子序列类区间 DP 直接合并。

02.7.2.1-004 石子合并(LC 1147 类)怎么推?

一句话结论

dp[i][j] 合并区间 [i,j] 全部石子的最小代价;枚举分割点,dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum(i,j);区间和用前缀和;单元素代价 0;时间 O(n³),空间 O(n²)。

概念解释

  • 合并代价:当前区间石子总和。
  • 最后一步:两堆合并。

原理流程

  1. 定义区间最小代价。
  2. 枚举最后合并的两堆。
  3. 加区间和。

代码 / 示例

for (int k = i; k < j; k++)
    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
dp[i][j] += prefix[j+1] - prefix[i];

常见误区

  • 误区:代价只加最上层;正解:每次合并都产生代价,逐层累加。
  • 误区:区间和重复计算;正解:前缀和 O(1) 求。

追问

  • Q:环形石子合并怎么办? A:破环为链复制一倍,见 02.7.2.1-014。
  • Q:复杂度? A:O(n³)。

02.7.2.1-005 戳气球(LC 312)为什么反向区间?

一句话结论

直接戳破后左右相邻关系改变,正向状态难维护;反向看最后留下的气球 k:先戳破 [i+1,k-1] 与 [k+1,j-1],最后戳 k,得分 nums[i]*nums[k]*nums[j];区间外包边界 i、j。

概念解释

  • 反向:最后戳的作为根。
  • 外包边界:两端哨兵。

原理流程

  1. 加左右哨兵 1。
  2. 定义开区间 (i,j) 最大得分。
  3. 枚举最后戳 k 合并。

代码 / 示例

for (int k = i + 1; k < j; k++)
    dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]);

常见误区

  • 误区:正向按戳破顺序 DP;正解:相邻关系变化,反向固定根更稳。
  • 误区:漏加哨兵边界;正解:两端补 1 处理边界气球。

追问

  • Q:复杂度? A:O(n³) 时间 O(n²) 空间。
  • Q:为什么最后戳 k 得分是三数乘积? A:此时左右邻居是 i、j。

02.7.2.1-006 矩阵链乘怎么求最少乘法次数?

一句话结论

dp[i][j] 矩阵 i~j 相乘最少标量乘法次数;枚举分割 k,代价 dp[i][k]+dp[k+1][j]+p[i-1]·p[k]·p[j];单矩阵代价 0;时间 O(n³)。

概念解释

  • 矩阵维度:p 数组相邻维度。
  • 合并代价:三维度乘积。

原理流程

  1. 定义区间最少次数。
  2. 枚举最后相乘的分界。
  3. 加本次乘法代价。

代码 / 示例

dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])

常见误区

  • 误区:代价维度取错;正解:左行数、中间列行、右列。
  • 误区:矩阵顺序可交换;正解:矩阵乘法不满足交换律。

追问

  • Q:复杂度? A:O(n³)。
  • Q:怎么记录最优括号? A:存分割点回溯。

02.7.2.1-007 最长回文子串区间 DP(LC 5)怎么做?

一句话结论

dp[i][j] 子串 [i,j] 是否回文;两端相等且内部 [i+1,j-1] 回文(或长度 ≤2)则为真;按长度填表,记录最长起止;时间 O(n²),空间 O(n²),中心扩展可 O(1) 空间。

概念解释

  • 连续回文。
  • 两端相等 + 内部回文。

原理流程

  1. 定义区间布尔。
  2. 长度 1/2 基准。
  3. 长区间两端相等且内部真。

代码 / 示例

if (s.charAt(i) == s.charAt(j) && (j-i <= 2 || dp[i+1][j-1]))
    dp[i][j] = true;

常见误区

  • 误区:长度 2 也查内部;正解:两相等即回文。
  • 误区:按 i 正序;正解:长度外层。

追问

  • Q:中心扩展复杂度? A:O(n²) 时间 O(1) 空间。
  • Q:与回文子序列区别? A:连续 vs 不连续。

02.7.2.1-008 回文串最少切割(LC 132)怎么做?

一句话结论

两阶段:先区间 DP 预处理 isPal[i][j] 回文表;再线性 DP dp[i] 前缀最少切割,枚举断点 j,[j,i) 回文则 dp[i]=min(dp[i], dp[j-1]+1);时间 O(n²)。

概念解释

  • 预处理:回文判定 O(1)。
  • 线性切割:前缀最少刀数。

原理流程

  1. 区间表判回文。
  2. 前缀 DP 枚举最后一段。
  3. 回文段转移。

代码 / 示例

dp[0] = -1; // 便于段数换算
for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
        if (isPal[j][i-1]) dp[i] = Math.min(dp[i], dp[j] + 1);

常见误区

  • 误区:切割数与段数混淆;正解:段数 -1 为刀数。
  • 误区:回文判断未预处理;正解:否则内层重复判回文超时。

追问

  • Q:复杂度? A:O(n²) 时间 O(n²) 空间。
  • Q:能边判回文边 DP 吗? A:可,按长度维护回文表。

02.7.2.1-009 博弈区间 DP:预测赢家(LC 486)怎么推?

一句话结论

dp[i][j] 当前玩家在区间 [i,j] 能拿到的相对优势(本方减对方);取左端则优势 nums[i]-dp[i+1][j],取右端 nums[j]-dp[i][j-1],取 max;基准 dp[i][i]=nums[i];时间 O(n²)。

概念解释

  • 零和博弈:相对优势。
  • 后手视角:子区间优势取反。

原理流程

  1. 定义区间相对分差。
  2. 两端选择减去后手优势。
  3. 先手优势 ≥0 即赢。

代码 / 示例

dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);

常见误区

  • 误区:存双方总分;正解:相对优势更易转移,后手优势取反。
  • 误区:基准为 0;正解:单元素优势即该元素值。

追问

  • Q:先手赢的判据? A:dp[0][n-1] ≥ 0。
  • Q:复杂度? A:O(n²)。

02.7.2.1-010 整数拆分乘积(LC 343)是区间 DP 吗?

一句话结论

整数拆分求最大乘积是线性/背包视角:dp[i] 把 i 拆分的最大乘积,枚举最后一段 j,dp[i]=max(j·dp[i-j], j·(i-j));不属于区间 DP,按线性 DP 处理。

概念解释

  • 线性状态:整数 i。
  • 拆分:最后一段 + 剩余拆分。

原理流程

  1. 定义拆分最大乘积。
  2. 枚举分段 j。
  3. 比较剩余拆与不拆。

代码 / 示例

for (int i = 2; i <= n; i++)
    for (int j = 1; j < i; j++)
        dp[i] = Math.max(dp[i], Math.max(j * dp[i-j], j * (i-j)));

常见误区

  • 误区:必须拆成至少两段;正解:剩余部分可不再拆。
  • 误区:按区间两端定义;正解:单值线性状态即可。

追问

  • Q:数学结论? A:优先拆 3,余数补 2。
  • Q:复杂度? A:O(n²)。

02.7.2.1-011 区间 DP 初始化怎么填?

一句话结论

单元素区间按题意填基准:最值类 0 或元素值,计数类 1,布尔类按单元素性质;更长区间先置哨兵(INF/-INF/false)再枚举分割更新;基准与状态定义一致。

概念解释

  • len=1 基准。
  • 哨兵:不可达初始值。

原理流程

  1. 填单元素区间。
  2. 长区间初始化哨兵。
  3. 分割更新覆盖。

代码 / 示例

for (int i = 0; i < n; i++) dp[i][i] = 0; // 合并类基准
// 最值长区间:dp[i][j] = INF

常见误区

  • 误区:长区间初始 0 参与取 min;正解:不可达用 INF。
  • 误区:单元素代价遗漏;正解:按题意填元素值或 0。

追问

  • Q:计数类单元素基准? A:通常 1 种。
  • Q:布尔类单元素? A:按单字符性质(回文 true)。

02.7.2.1-012 区间合并代价怎么计算?

一句话结论

合并代价由题目给定:区间石子和、矩阵三乘积、两端字符组合等;通常可用前缀和 O(1) 求区间和;代价在分割合并时加入,不重复计入子区间。

概念解释

  • 本层代价:最后一次合并。
  • 子区间代价:已在 dp 内。

原理流程

  1. 识别最后一步操作。
  2. 计算本层代价。
  3. 加左右子区间结果。

代码 / 示例

cost = prefix[j+1] - prefix[i]; // 区间和

常见误区

  • 误区:每层都加全区间和导致重复;正解:子区间代价已含,只加本层合并。
  • 误区:前缀和下标错位;正解:[i,j] 为 prefix[j+1]-prefix[i]。

追问

  • Q:代价与顺序有关吗? A:按题,合并顺序影响总代价。
  • Q:代价为 0 的题? A:直接合并子区间最值。

02.7.2.1-013 区间 DP 记忆化写法怎么写?

一句话结论

dfs(i,j) 返回区间结果,枚举 k 递归左右子区间并缓存; memo 二维数组记录;基准命中直接返回;无需手动排长度,递归天然先算子区间。

概念解释

  • 自顶向下区间。
  • memo 缓存区间值。

原理流程

  1. 查 memo 命中返回。
  2. 基准直接给值。
  3. 枚举 k 递归合并回填。

代码 / 示例

int dfs(int i, int j) {
    if (i == j) return base;
    if (memo[i][j] != -1) return memo[i][j];
    for (int k = i; k < j; k++) memo[i][j] = opt(...);
    return memo[i][j];
}

常见误区

  • 误区:memo 哨兵与合法值冲突;正解:选不冲突标记。
  • 误区:递归深度过长;正解:区间递归深度 O(n),一般可控。

追问

  • Q:记忆化与填表结果一致吗? A:一致,方向相反。
  • Q:状态稀疏时哪种省? A:记忆化只算可达区间。

02.7.2.1-014 环形区间怎么破环为链?

一句话结论

环形问题复制一倍数组接在尾部,长度扩为 2n,在长度 n 的窗口上做区间 DP;覆盖“首尾相连”的所有线性切法;最后在所有长度 n 区间中取答案。

概念解释

  • 破环:展开成链。
  • 窗口:长度 n。

原理流程

  1. 数组复制一倍。
  2. 区间 DP 在 2n 上进行。
  3. 取长度 n 的最优区间。

代码 / 示例

a + a;对所有起点 s,区间 [s, s+n-1] 求最优

常见误区

  • 误区:只处理从 0 切开;正解:环可在任意位置断开,需遍历窗口。
  • 误区:扩展后长度超界;正解:终点限制在 2n-1 内。

追问

  • Q:环形打家劫舍也是破环吗? A:是,拆两段线性,思路等价。
  • Q:复杂度? A:O(n³) 区间在 2n 上。

02.7.2.1-015 区间 DP 复杂度 O(n³) 怎么来的?

一句话结论

区间状态 O(n²),每个区间枚举分割点 k 最坏 O(n),相乘 O(n³);空间 O(n²);若转移 O(1) 无分割点则为 O(n²)。

概念解释

  • 状态数:n² 区间。
  • 转移:枚举 k。

原理流程

  1. 数区间 O(n²)。
  2. 单区间 O(n) 分割。
  3. 相乘得 O(n³)。

代码 / 示例

n² 区间 × n 分割点 = O(n³)

常见误区

  • 误区:区间 DP 报 O(n²);正解:含分割点枚举是 O(n³)。
  • 误区:忽略空间 n²;正解:状态表 O(n²)。

追问

  • Q:什么区间题是 O(n²)? A:无分割点,两端直接转移。
  • Q:n 多大 O(n³) 可行? A:n 百级以内。

02.7.2.1-016 区间 DP 与子序列 DP 怎么区分?

一句话结论

区间 DP 状态是连续端点 [i,j],转移按区间分割或两端取舍;子序列 DP 多为双前缀状态,匹配可跳跃;回文两类都可能:连续回文用区间连续判定,回文子序列不连续。

概念解释

  • 连续区间:端点界定连续段。
  • 子序列:前缀匹配可跳跃。

原理流程

  1. 判断是否要求连续。
  2. 连续归区间 DP。
  3. 不连续归子序列 DP。

代码 / 图示

区间:dp[i][j] 连续段;子序列:dp[i][j] 双前缀

常见误区

  • 误区:回文题一律区间;正解:子序列不连续转移不同。
  • 误区:区间枚举 k 用于子序列;正解:子序列无需分割点。

追问

  • Q:戳气球为什么区间? A:固定区间内操作,相邻关系封闭。
  • Q:LCS 为什么不是区间? A:两串各自前缀匹配。

02.7.2.1-017 最优分割决策点怎么记录?

一句话结论

填表时把取得最优的分割点 k 存入 opt[i][j];结束后从完整区间沿 opt 递归回溯,得到最优分割方案;只需求最值可不记录。

概念解释

  • opt 表:最优分割位置。
  • 回溯还原。

原理流程

  1. 更新最值时记录 k。
  2. 终态沿 opt 下钻。
  3. 输出分割结构。

代码 / 示例

if (better) { dp[i][j] = ...; opt[i][j] = k; }

常见误区

  • 误区:一维压缩后记录分割点;正解:需保留二维 opt 表。
  • 误区:等值分割点任选不一致;正解:按规则记录其一。

追问

  • Q:记录 opt 增加多少空间? A:O(n²)。
  • Q:方案有多条怎么办? A:存全部 opt 或回溯枚举。

02.7.2.1-018 区间 DP 常见枚举错误有哪些?

一句话结论

高频错误:按 i 正序导致子区间未就绪、分割点越界、单元素基准漏填、长区间哨兵选错、区间和下标错位;按长度外层、k∈[i,j-1]、基准先填逐项核对。

概念解释

  • 顺序:长度外层。
  • 边界:分割点与基准。

原理流程

  1. 检查填表顺序。
  2. 核对 k 范围。
  3. 补基准与哨兵。

代码 / 示例

排查:长度顺序 / k 范围 / 单元素基准 / 哨兵 / 区间和下标

常见误区

  • 误区:len 从 2 起未填 len=1;正解:先填基准。
  • 误区:k=j 产生空右区间;正解:k<j。

追问

  • Q:结果偏大先查什么? A:代价重复计入或哨兵错误。
  • Q:结果偏小先查什么? A:分割点遗漏或基准错误。

02.7.2.1-019 回文判定预处理怎么加速?

一句话结论

先用区间 DP 求出 isPal[i][j] 布尔表:两端相等且内部回文;后续切割/计数题 O(1) 查区间是否回文,避免内层重复双指针判断;预处理 O(n²)。

概念解释

  • 预处理表。
  • O(1) 查询。

原理流程

  1. 单字符与相邻相等填表。
  2. 长度递增推长区间。
  3. 后续 DP 查表。

代码 / 示例

isPal[i][i] = true;
isPal[i][i+1] = s.charAt(i)==s.charAt(i+1);
// 长区间:两端相等 && isPal[i+1][j-1]

常见误区

  • 误区:预处理顺序反向;正解:按长度递增。
  • 误区:长度 2 未单独处理;正解:内部区间为空需特判。

追问

  • Q:预处理空间? A:O(n²),可按长度滚动。
  • Q:哪些题受益? A:回文切割、回文计数类。

02.7.2.1-020 区间 DP 怎么判断该不该用?

一句话结论

问题按连续区间分解、最后一步把区间切成两段(或取舍两端)、子区间独立可合并时,用区间 DP;若状态是前缀/结尾/容量则归线性 DP,若结构是树则归树形 DP。

概念解释

  • 连续区间分解。
  • 两段合并。

原理流程

  1. 看子问题是否为连续区间。
  2. 看末步是否分割/取端。
  3. 对照其他 DP 类型排除。

代码 / 图示

连续段 + 分割合并 → 区间 DP
前缀/结尾 → 线性;树上 → 树形

常见误区

  • 误区:看到双端点就套区间;正解:先确认子问题是连续区间。
  • 误区:区间 DP 硬套不可分割的题;正解:无两段合并则换状态。

追问

  • Q:戳气球为什么区间适用? A:固定外包区间内最后戳一个。
  • Q:区间 DP 一般 n 多大? A:O(n³) 适合 n 百级以内。