区间 DP (Interval DP)

[!abstract] 核心思想 在区间上进行 DP，通过小区间的最优解推导出大区间的最优解。

---

模板

// 区间 DP 一般结构
for (let len = 2; len <= n; len++) {        // 枚举区间长度
  for (let i = 0; i + len - 1 < n; i++) {   // 枚举起点
    const j = i + len - 1;                   // 区间终点
    for (let k = i; k < j; k++) {            // 枚举分割点
      dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j));
    }
  }
}

---

1. 合并石子

问题

• n 堆石子，每次合并相邻两堆，代价为两堆之和，求最小代价

function minCostMergeStones(stones: number[]): number {
  const n = stones.length;
  if (n === 1) return 0;

  // 前缀和
  const prefix = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + stones[i - 1];
  }

  // dp[i][j] = 合并区间 [i, j] 的最小代价
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  // 区间长度从 2 到 n
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;

      // 枚举分割点
      for (let k = i; k < j; k++) {
        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i]);
      }
    }
  }

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

图解

石子: [3, 2, 4, 1]

合并过程:
  (3,2) -> 5      (4,1) -> 5
       \          /
        \        /
         \      /
          [5,4,1] -> 10
             |
          [5,10] -> 15

总代价: 5 + 5 + 10 + 15 = 35

---

2. 戳气球

问题

• 戳破气球获得硬币，气球 i 和 j 之间的气球被戳破时获得 nums[i] * nums[k] * nums[j]

function maxCoins(nums: number[]): number {
  const n = nums.length;
  // 虚拟气球作为边界
  const vals = [1, ...nums, 1];
  const dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));

  // 区间长度从 1 到 n
  for (let len = 1; len <= n; len++) {
    for (let i = 1; i + len - 1 <= n; i++) {
      const j = i + len - 1;
      for (let k = i; k <= j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k - 1] + dp[k + 1][j] + vals[i - 1] * vals[k] * vals[j + 1]
        );
      }
    }
  }

  return dp[1][n];
}

区间依赖关系

---

3. 括号化

问题

• 给表达式添加括号使其值最大

function maxParenthesis(expr: string, values: number[]): number {
  const n = values.length;
  // dp[i][j] = 区间 [i, j] 的最大价值
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  const ops = Array.from({ length: n }, () => Array(n).fill<number[][]>([]));

  // 记录每个区间可能的值
  for (let i = 0; i < n; i++) {
    dp[i][i] = values[i];
    ops[i][i] = [values[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] = -Infinity;

      for (let k = i; k < j; k++) {
        // ops[i][k] 和 ops[k+1][j] 的笛卡尔积
        for (const left of ops[i][k]) {
          for (const right of ops[k + 1][j]) {
            const result = expr[k] === '+'
              ? left + right
              : left * right;
            dp[i][j] = Math.max(dp[i][j], result);
          }
        }
      }

      // 收集所有可能值用于后续计算
      ops[i][j] = [];
      for (let k = i; k < j; k++) {
        for (const left of ops[i][k]) {
          for (const right of ops[k + 1][j]) {
            const result = expr[k] === '+'
              ? left + right
              : left * right;
            ops[i][j].push(result);
          }
        }
      }
    }
  }

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

---

4. 博弈类区间DP

问题

• 先手 vs 后手，谁更优？

function predictWinner(nums: number[]): boolean {
  const n = nums.length;
  // dp[i][j] = 在区间 [i, j] 先手能获得的最大分数
  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;
      // 选择左边或右边，然后对方变成先手
      const pickLeft = nums[i] + (dp[i + 1][j] - Math.max(0, nums[j] - nums[i + 1] || 0));
      const pickRight = nums[j] + (dp[i][j - 1] - Math.max(0, nums[i] - nums[j - 1] || 0));

      // 实际上更简单的转移
      dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
    }
  }

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

---

5. 合并所有果子（哈夫曼编码类）

// 使用贪心，但也可以用 DP（不常用）
// 实际上这是哈夫曼编码，最优解是贪心
function minCostMergeStones_Huffman(stones: number[]): number {
  const pq = [...stones].sort((a, b) => a - b);
  let cost = 0;

  while (pq.length > 1) {
    const a = pq.shift()!;
    const b = pq.shift()!;
    const sum = a + b;
    cost += sum;
    pq.push(sum);
    pq.sort((a, b) => a - b);
  }

  return cost;
}

---

典型问题列表

题目	核心思路
合并石子	枚举分割点 + 前缀和
戳气球	逆序思考，最后戳破 k
括号化	笛卡尔积枚举
博弈论	dp[i][j] = max/min(选左/选右 + 对方)
统计回文子串	区间扩张

---

参见: **DP算法索引** | **基础问题**