动态规划：区间与划分模型

有一类 DP 题，既不像背包，也不像双序列。它们更像是在问：

1. 一个区间 [i, j] 上的答案是什么？
2. 如果在中间切一刀，左右两边能不能拼出最优答案？
3. 先解决短区间，再解决长区间，能不能推出全局结果？

这就是区间 / 划分 DP。

解题决策树

拿到一道字符串 / 区间最优值问题
│
├─ 状态天然是一个区间 `[i, j]`？
│  └─ 是 → 区间 DP ............................ → 见「一」
│
├─ 题目需要在某处切开，再合并左右答案？
│  └─ 是 → 划分 DP ............................ → 见「二」
│
├─ 两个人轮流取区间两端，问胜负或最优值？
│  └─ 是 → 博弈型区间 DP ...................... → 见「三」
│
└─ 状态不是区间本身，而是两个前缀？
   └─ 更接近双序列 DP ......................... → 见「序列与双序列模型」

一、区间 DP

判断关键词：回文、子串、区间最值、从短区间推出长区间。

区间 DP 最常见的状态定义是：

dp[i][j] = 子串 / 子数组 nums[i...j] 的答案

1.1 最常见模板

function intervalDp(s: string): void {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));

  for (let len = 1; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = transition(dp, s, i, j);
    }
  }
}

为什么要按区间长度遍历？ 因为 dp[i][j] 往往依赖更短的区间，例如 dp[i + 1][j - 1]。

1.2 回文区间

function longestPalindrome(s: string): string {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(false));
  let start = 0;
  let maxLen = 1;

  for (let len = 1; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      if (s[i] === s[j] && (len <= 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (len > maxLen) {
          maxLen = len;
          start = i;
        }
      }
    }
  }

  return s.slice(start, start + maxLen);
}

题型参考：

题目	状态定义
[5] 最长回文子串	dp[i][j] = s[i...j] 是否为回文。
[516] 最长回文子序列	dp[i][j] = 区间内最长回文子序列长度。

二、划分 DP

判断关键词：切分、分段、把区间分成左右两部分、枚举分割点。

这类题比普通区间 DP 多一个动作：

1. 枚举切分点 k。
2. 用左边答案和右边答案合成当前答案。

3.1 通用模板

function splitDp(nums: number[]): number {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let len = 1; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = initialValue(i, j);

      for (let k = i; k < j; k++) {
        dp[i][j] = merge(dp[i][j], dp[i][k], dp[k + 1][j], i, k, j);
      }
    }
  }

  return dp[0][n - 1];
}

常见题型

题目	关键思路
[132] 分割回文串 II	先预处理回文，再做最少切分。
[87] 扰乱字符串	枚举切分点，比较两边能否匹配。
[375] 猜数字大小 II	枚举第一次猜哪一个，取最坏情况下的最小代价。

注意： 有些划分题不一定写成 dp[i][j]，也可能写成一维前缀 DP，但本质仍然是“枚举最后一刀 / 第一刀”。

三、博弈型区间 DP

判断关键词：两个人轮流取数、从两端拿、双方都最优。

这类题的重点不只是区间，还要明确“当前轮到谁”。

常见做法是把 dp[i][j] 定义成：

1. 当前玩家在区间 [i, j] 相对对手的最大分差。
2. 或当前玩家在区间 [i, j] 能拿到的最优值。

通用模板

function gameDp(nums: number[]): number {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) {
    dp[i][i] = nums[i];
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
    }
  }

  return dp[0][n - 1];
}

题型参考：

题目	关键思路
[877] 石子游戏	dp[i][j] 表示先手相对后手的最大优势。

四、区间 DP 的遍历顺序为什么重要

区间 DP 大多依赖“更短的区间”，所以遍历顺序通常只有两种稳定写法：

1. 按区间长度从小到大。
2. 按左端点从大到小、右端点从小到大。

只要保证 dp[i][j] 所依赖的区间已经算过，就可以。

五、如何判断它是不是区间/划分 DP

可以用这 3 个问题快速判断：

1. 如果我知道所有更短区间的答案，能不能推出当前区间？
2. 当前答案是不是和“切分点 k”有关？
3. 子问题天然是不是一个连续区间？

如果答案大多是“是”，就应该优先考虑区间 / 划分 DP。

易错点清单

1. dp[i][j] 的含义不清楚，结果既像长度又像布尔值。
2. 遍历顺序错了，先算了长区间，短区间还没准备好。
3. 划分题漏掉枚举分割点 k。
4. 明明是双序列前缀问题，却误写成区间 DP。
5. 博弈题没把“对手也最优”体现在转移式里。

总结：解题速查表

题目特征	优先 DP 模型	核心状态
回文、子串、区间最值	区间 DP	dp[i][j]
切分、枚举分割点	划分 DP	dp[i][j] 或前缀 DP
两端取数、双方博弈	博弈型区间 DP	dp[i][j]
当前答案依赖更短区间	区间 / 划分 DP	长度递增遍历