区间 DP 与状态压缩：进阶状态设计

我真正开始理解“区间 DP 与状态压缩：进阶状态设计”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：区间 DP 和状态压缩第一次出现在我面前时都很抽象，一个不知道按什么长度枚举，一个不知道二进制位如何对应选择。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

区间 DP 和状态压缩 DP 都属于动态规划里的进阶内容。它们看起来比线性 DP 难，是因为状态组织方式变了。

线性 DP 通常按位置推进；区间 DP 按区间长度推进；状态压缩 DP 则用二进制位表示集合状态。

两种进阶状态

区间 DP 与状态压缩

图：区间 DP 先算小区间，状态压缩用 bitmask 表示集合

区间 DP

区间 DP 的状态通常是：

dp[l][r] 表示区间 [l, r] 的最优结果

它常见于：

合并石子。
戳气球。
回文区间。
矩阵链乘法。
区间博弈。

区间 DP 的遍历顺序通常是先枚举长度：

for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        for (int k = l; k < r; k++) {
            dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost);
        }
    }
}

为什么按长度？因为大区间依赖小区间。先算长度小的，才能推出长度大的。

回文区间

判断字符串子串是否回文：

boolean[][] isPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int len = 1; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s.charAt(l) == s.charAt(r)) {
                dp[l][r] = len <= 2 || dp[l + 1][r - 1];
            }
        }
    }
    return dp;
}

dp[l][r] 依赖 dp[l+1][r-1]，所以必须先算更短区间。

状态压缩 DP

当元素数量不大，但集合组合很多时，可以用二进制位表示集合。

例如 mask = 1011 表示第 0、1、3 个元素已经被选择。

常见操作：

boolean selected = (mask & (1 << i)) != 0;
int add = mask | (1 << i);
int remove = mask & ~(1 << i);

状态压缩常用于：

旅行商问题。
小规模任务分配。
集合覆盖。
状态枚举。
棋盘压缩。

旅行商问题简化版

dp[mask][i] 表示已经访问集合 mask，并且最后停在 i 的最小成本。

int tsp(int[][] dist) {
    int n = dist.length;
    int INF = 1_000_000_000;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, INF);
    dp[1][0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) continue;
                int next = mask | (1 << j);
                dp[next][j] = Math.min(dp[next][j], dp[mask][i] + dist[i][j]);
            }
        }
    }
    int ans = INF;
    int full = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, dp[full][i] + dist[i][0]);
    }
    return ans;
}

状态压缩 DP 的复杂度常常是 O(2^n * n²)，所以只适合 n 较小的情况。

常见错误

区间 DP 没按长度遍历，导致依赖状态还没算。
区间边界 l/r 越界。
状态压缩里 1 << n 溢出。
忘记判断某个元素是否在 mask 中。
状态定义缺少“最后停在哪里”这类关键信息。
对大规模问题误用状态压缩，直接内存爆炸。

工程场景

区间 DP 适合有明显连续区间的问题，如文本分段、合并成本、解析器里的区间结构。状态压缩适合元素不多但组合复杂的任务，比如小规模排班、权限组合、测试组合选择。

工程中如果 n 稍微大一点，状态压缩就可能不可用。此时要考虑剪枝、启发式搜索、近似算法或交给专门优化器。

面试题

区间 DP 为什么通常要按区间长度枚举？
dp[l][r] 常见含义是什么？
状态压缩为什么适合小 n？
mask 如何判断第 i 个元素是否被选择？
状态压缩 DP 为什么经常还需要记录最后位置？

小结

区间 DP 和状态压缩 DP 都是在重新组织状态。前者把连续范围作为状态，后者把集合选择作为状态。它们难在状态设计，不难在代码模板。先画清楚依赖关系，再写转移，才不会迷路。