枚举分割点的 dp

什么样的题适合枚举分割点？

• 特征: 一个规模为 i 的问题可以拆成"左半部分 + 当前分割点"或"两个子规模之和";
• 状态: dp[i] 表示规模为 i 的最优值或方案数;
• 内层: 枚举分割点 j, 合并两侧结果;
• 复杂度: 两层循环, 一般 O(n^2);

整数拆分如何枚举分割点？

• 问题: 把正整数拆成至少两个正整数之和, 使乘积最大 (343);
• 状态: dp[i] 为 i 拆分后的最大乘积;
• 决策: 第一个因子取 j (1 <= j < i), 剩余部分 i-j 有两种选择;
  • 不再拆: 乘积为 j * (i - j);
  • 继续拆: 乘积为 j * dp[i-j];
• 方程: dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);
• 初值: dp[0] = dp[1] = 0, 两者无法拆分;
• 答案: dp[n];

const integerBreak = (n) => {
  const dp = new Array(n + 1).fill(0);
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      dp[i] = Math.max(dp[i], (i - j) * j, dp[i - j] * j);
    }
  }
  return dp[n];
};

不同的二叉搜索树如何枚举分割点？

• 问题: 求 n 个节点能构成多少种结构不同的二叉搜索树 (96);
• 状态: dp[i] 为 i 个节点能构成的二叉搜索树数量;
• 决策: 枚举根节点的排名 j (1 <= j <= i);
  • 左子树有 j-1 个节点, 右子树有 i-j 个节点;
  • 左右子树结构相互独立, 方案数相乘;
• 方程: dp[i] += dp[j-1] * dp[i-j];
• 初值: dp[0] = 1, 表示空树也算一种结构;
• 答案: dp[n];

const numTrees = (n) => {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) dp[i] += dp[j - 1] * dp[i - j];
  }
  return dp[n];
};

两个问题为什么形式相同？

• 共同点: 都在规模 i 上枚举切分位置, 把问题分成两个独立子规模;
• 差别: 整数拆分合并时取乘积最大值, 二叉搜索树合并时取方案数相乘再求和;
• 推广: 只要满足"子问题独立 + 可合并", 都能套用这一结构, 如矩阵连乘、多边形三角剖分 (见 区间 dp);