区间 DP

区间 DP 将连续子段作为状态，常用于合并、分割、消去或括号化问题。令 dp[l][r] 表示闭区间 [l,r] 的最优答案。

转移与顺序

枚举区间长度从小到大，使转移使用的子区间已经计算。若在 k 处分割，常见式子为 dp[l][r]=min/max(dp[l][k]+dp[k+1][r]+cost(l,k,r))。

for (int len=2; len<=n; ++len)
  for (int l=1; l+len-1<=n; ++l) {
    int r=l+len-1; dp[l][r]=INF;
    for (int k=l; k<r; ++k)
      dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
  }

石子合并

把 [l,r] 最后一次合并切为两段，代价为两段最优代价加本区间石子和；前缀和让区间和 O(1) 获得。dp[i][i]=0 是长度为 1 的边界。

复杂度与要点

n² 个区间、每个枚举 n 个断点，通常为 O(n³) 时间、O(n²) 空间。矩阵链乘、回文删除和戳气球都可按“最后一次操作”构造区间状态；开放区间写法可在两端加入哨兵，减少边界讨论。

整理自 XOJ《区间DP》。