区间合并与括号匹配

戳气球如何用区间合并建模？

• 问题: 戳破气球获得 左右相邻气球值 * 自身值 的硬币, 求最大总收益 (312);
• 边界补全: 数组两端各补一个值为 1 的虚拟气球, 使越界情形也有邻居;
• 状态: dp[i][j] 为戳破开区间 (i, j) 内全部气球获得的最大硬币数;
• 关键视角: 反过来想"某个气球是区间内最后被戳破的";
• 转移: 设最后戳破的气球为 k (i < k < j), 则 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[j] * nums[k]);
• 初值: 全部为 0 (区间内没有气球时收益为 0);
• 遍历: 按区间长度从 3 开始递增 (两端是虚拟气球), 再枚举起点与分割点;
• 答案: dp[0][size-1];
• 复杂度: 时间 O(n^3), 空间 O(n^2);

const maxCoins = (nums) => {
  const arr = [1, ...nums, 1];
  const size = arr.length;
  const dp = Array.from({ length: size }, () => new Array(size).fill(0));
  for (let len = 3; len <= size; len++) {
    for (let i = 0; i + len - 1 < size; i++) {
      const j = i + len - 1;
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[j] * arr[k]);
      }
    }
  }
  return dp[0][size - 1];
};

为什么按"最后一个戳破"定义反而简单？

• 正向难点: 戳破一个气球会改变左右邻居, 后续收益依赖已戳顺序, 存在后效性;
• 逆向优势: 最后戳破的 k 在被戳时左右边界 i、j 一定还在, 收益被唯一确定, 无后效;
• 结论: 区间 dp 常通过"最后一次操作"消掉后效性;

有效的括号字符串如何用区间 dp 判定？

• 问题: 字符串含 (, ), *, 判断能否构成合法括号串, * 可当 (、) 或空 (678);
• 状态: dp[i][j] 表示 s[i..j] 是否为有效字符串;
• 长度 1: 仅当 s[i] === "*" (当作空) 时为真;
• 长度 2: 左右分别可为左括号与右括号 (含 * 的通配) 时为真;
• 更长: 两种来源;
  • 单段匹配: 两端配对后看内部, dp[i][j] = dp[i+1][j-1];
  • 多段拼接: 存在分割点 k 使 dp[i][k] && dp[k+1][j];
• 初值: 全部为 false;
• 答案: dp[0][n-1];
• 复杂度: 时间 O(n^3), 空间 O(n^2);

const checkValidString = (s) => {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (i === j) {
        dp[i][j] = s[i] === "*";
        continue;
      }
      const pair = (s[i] === "(" || s[i] === "*") && (s[j] === ")" || s[j] === "*");
      if (!pair) continue;
      if (i + 1 === j) dp[i][j] = true;
      else {
        dp[i][j] = dp[i + 1][j - 1];
        for (let k = i; k < j && !dp[i][j]; k++) dp[i][j] = dp[i][k] && dp[k + 1][j];
      }
    }
  }
  return dp[0][n - 1];
};

拼接型区间 dp 的分割点如何枚举？

• 含义: 把区间切成左右两段分别判定, 再要求同时成立;
• 范围: k 从 i 到 j-1, 保证两段都非空;
• 提前退出: 一旦某次 k 使条件成立即可跳出, 避免无效枚举;