状态压缩 DP (State Compression DP)

[!abstract] 核心思想 用二进制位表示状态，将「n 个元素的选择情况」压缩为一个整数。

---

基础操作

// 位运算技巧
const n = 5;

// 检查第 i 位是否为 1
function hasBit(state: number, i: number): boolean {
  return (state & (1 << i)) !== 0;
}

// 设置第 i 位为 1
function setBit(state: number, i: number): number {
  return state | (1 << i);
}

// 清除第 i 位
function clearBit(state: number, i: number): number {
  return state & ~(1 << i);
}

// 枚举子集
function* subsets(state: number) {
  let sub = state;
  while (sub) {
    yield sub;
    sub = (sub - 1) & state; // 下一个子集
  }
}

// 添加第 i 位的值
const val = 5; // 状态中添加了某物，价值增加

---

1. 旅行商问题 (TSP)

问题

• 从 0 出发，访问所有城市恰好一次，回到 0 的最短路径

function travelingSalesman(dist: number[][]): number {
  const n = dist.length;
  if (n === 0) return 0;

  // dp[mask][i] = 已访问状态为 mask，最后在 city i 的最小距离
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    Array(n).fill(Infinity)
  );

  dp[1][0] = 0; // mask=1 表示访问了 city 0

  // 枚举所有状态
  for (let mask = 0; mask < (1 << n); mask++) {
    for (let last = 0; last < n; last++) {
      if (dp[mask][last] === Infinity) continue;

      // 尝试去下一个城市
      for (let next = 0; next < n; next++) {
        if (!(mask & (1 << next))) { // next 还没去过
          const newMask = mask | (1 << next);
          dp[newMask][next] = Math.min(
            dp[newMask][next],
            dp[mask][last] + dist[last][next]
          );
        }
      }
    }
  }

  const fullMask = (1 << n) - 1;
  let ans = Infinity;
  for (let last = 1; last < n; last++) {
    ans = Math.min(ans, dp[fullMask][last] + dist[last][0]);
  }

  return ans;
}

图解

n=3 城市: 0, 1, 2

状态转移:
  mask=001 (只去0) -> 010 (去0,1) -> 100 (去0,1,2)
                -> 100 (直接去2) -> 010 (去0,2,1)

  dp[mask][last] = min(dp[prev][k] + dist[k][last])

---

2. 炮兵阵地

问题

• 在网格上放置炮兵，互相不能攻击，求最多放置数

function canPlace(mountain: string[], m: number, n: number): boolean {
  // 检查某行状态是否与山脉冲突
  const valid = (rowMask: number) => {
    for (let i = 0; i < n; i++) {
      if ((rowMask & (1 << i)) && mountain[rowMask][i] === 'H') {
        return false;
      }
    }
    return true;
  };

  // 两行状态是否兼容（炮兵攻击范围 2 格）
  const compatible = (a: number, b: number) => {
    if (a & b) return false;
    if (a & (b << 1)) return false;
    if (a & (b >> 1)) return false;
    return true;
  };

  // 找出所有可行的行状态
  const states: number[] = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    if (valid(mask)) states.push(mask);
  }

  // dp[row][state] = 到第 row 行，当前行状态为 state 的最大值
  const prev = Array(1 << n).fill(0);

  for (let r = 0; r < m; r++) {
    const curr = Array(1 << n).fill(0);
    for (const curState of states) {
      for (const prevState of states) {
        if (!compatible(curState, prevState)) continue;
        curr[curState] = Math.max(curr[curState], prev[prevState]);
      }
      curr[curState] += __builtin_popcount(curState);
    }
    prev.splice(0, prev.length, ...curr);
  }

  return Math.max(...prev);
}

---

3. 蒙德里安的梦想

问题

• 用 1×2 多米诺骨牌覆盖 N×M 棋盘的方法数

function dominosCovering(n: number, m: number): number {
  // n 行, m 列
  // dp[mask] = 达到某列状态的方法数
  // mask 表示当前列的格子是否被上一列的骨牌填充

  const fullMask = (1 << n) - 1;
  const dp: bigint[] = Array(1 << n).fill(BigInt(0));
  dp[0] = BigInt(1);

  for (let col = 0; col < m; col++) {
    const next: bigint[] = Array(1 << n).fill(BigInt(0));

    for (let mask = 0; mask <= fullMask; mask++) {
      if (dp[mask] === BigInt(0)) continue;

      // 递归尝试填充空格
      const fill = (state: number) => {
        // 找到第一个空格
        const i = state ? Math.ctz(state) : -1; // __builtin_ctz
        if (i === -1) {
          next[mask] += dp[mask];
          return;
        }

        // 横放
        if (i + 1 < n && (state & (1 << (i + 1)))) {
          const newState = state ^ (1 << i) ^ (1 << (i + 1));
          fill(newState);
        }

        // 竖放
        if (i > 0 && (state & (1 << (i - 1)))) {
          // 不支持，需要额外参数
        }
      };

      // 简化：直接转移
    }
  }

  return Number(dp[fullMask]);
}

---

4. 哈密顿路径

问题

• 判断是否存在哈密顿路径

function hamiltonianPath(graph: number[][], n: number): boolean {
  const dp: boolean[][] = Array.from({ length: 1 << n }, () =>
    Array(n).fill(false)
  );

  // 初始化：每个点作为起点
  for (let i = 0; i < n; i++) {
    dp[1 << i][i] = true;
  }

  // 枚举状态
  for (let mask = 0; mask < (1 << n); mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      if (!dp[mask][last]) continue;

      // 尝试添加新节点
      for (let next = 0; next < n; next++) {
        if (mask & (1 << next)) continue;
        if (!graph[last][next]) continue;

        dp[mask | (1 << next)][next] = true;
      }
    }
  }

  const fullMask = (1 << n) - 1;
  for (let i = 0; i < n; i++) {
    if (dp[fullMask][i]) return true;
  }

  return false;
}

---

5. 集合划分

问题

• 将数组分成 k 个子集，求最小最大子集和

function partitionKSubsets(nums: number[], k: number): number {
  const n = nums.length;
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k !== 0) return -1;

  const target = total / k;
  const dp: number[] = Array(1 << n).fill(-1);
  dp[0] = 0;

  // 预处理：每个状态的元素和
  const sum = Array(1 << n).fill(0);
  for (let mask = 1; mask < (1 << n); mask++) {
    const bit = __builtin_ctz(mask);
    sum[mask] = sum[mask ^ (1 << bit)] + nums[bit];
  }

  // 如果和超过 target，该状态无效
  for (let mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] >= 0) {
      // 已经分成了 dp[mask] 个桶
      for (let i = 0; i < n; i++) {
        if (!(mask & (1 << i))) {
          const next = mask | (1 << i);
          if (sum[next] <= target) {
            if (dp[next] === -1) {
              dp[next] = dp[mask] + 1;
            }
          }
        }
      }
    }
  }

  return dp[(1 << n) - 1] === k ? target : -1;
}

---

复杂度分析

问题	状态数	转移	总复杂度
TSP	O(2^n × n)	O(n)	O(n² × 2^n)
炮兵	O(m × 2^n)	O(2^n × 状态)	O(m × 3^n)
哈密顿	O(2^n × n)	O(n)	O(n² × 2^n)

注意

状态压缩 DP 复杂度通常是指数级，适用于 n ≤ 20-25 的问题

---

参见: **DP算法索引** | **树形DP**