插头 DP (Plug DP / Parenthesis DP)

[!abstract] 核心思想 解决「在网格棋盘上遍历路径」的问题，通过状态压缩记录轮廓线的连通性。

---

问题背景

经典问题

• 哈密尔顿路径
• 回路覆盖棋盘
• 一笔画问题

核心概念

轮廓线: 当前位置右边和下方的边界线

┌───┬───┐
│   │   │  ← 轮廓线（虚线）
├───┼───┤
│   │   │
└───┴───┘

---

状态表示

// 每个格子用 2 个插头（左/上）
// 用 0/1 表示是否存在插头

// 例如：4 连通性用 3 进制
// 0 = 无插头
// 1 = 左插头（轮廓线左边）
// 2 = 右插头（轮廓线右边）

// 括号匹配用 4 进制
// 0 = 无
// 1 = 左括号
// 2 = 右括号
// 3 = 独立插头

---

模板框架

function plugDP(grid: boolean[][]): number {
  const m = grid.length, n = grid[0].length;

  // dp[state] = 到达当前轮廓线状态的方案数
  const dp: Map<number, number> = new Map();
  dp.set(0, 1);

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const newDp: Map<number, number> = new Map();

      for (const [state, cnt] of dp) {
        // 提取当前格子的状态
        const left = (state >> ((n - j) * 2)) & 3;
        const up = (state >> ((n - j - 1) * 2)) & 3;

        if (grid[i][j]) {
          // 格子可用

          // 情况1：都不连
          if (left === 0 && up === 0) {
            // 尝试放置
          }

          // 情况2：只有一个
          // ...

        } else {
          // 格子不可用，只能让插头穿过
          if ((left === 0) !== (up === 0)) {
            // 转移
          }
        }
      }

      dp.clear();
      for (const [k, v] of newDp) dp.set(k, v);
    }

    // 处理换行
    // ...
  }

  return dp.get(0) || 0;
}

---

1. 蒙德里安的梦想

问题

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

function dominos(n: number, m: number): number {
  // dp[mask] = 达到某列状态的方法数
  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 < (1 << n); mask++) {
      if (dp[mask] === BigInt(0)) continue;

      // 尝试填充当前列
      fill(0, mask, 0);
    }

    // 换行
    for (let mask = 0; mask < (1 << n); mask++) {
      if (isValidCol(mask)) {
        next[mask] += dp[mask];
      }
    }

    dp.splice(0, dp.length, ...next);
  }

  return Number(dp[0]);

  function fill(row: number, curMask: number, newMask: number) {
    if (row === n) {
      next[newMask] += dp[mask];
      return;
    }

    // 跳过已填充的格子
    if ((curMask & (1 << row)) !== 0) {
      fill(row + 1, curMask, newMask);
      return;
    }

    // 横放
    if (row + 1 < n && (curMask & (1 << (row + 1))) === 0) {
      fill(row + 2, curMask, newMask | (1 << row) | (1 << (row + 1)));
    }

    // 竖放
    fill(row + 1, curMask | (1 << row), newMask | (1 << row));
  }

  function isValidCol(mask: number): boolean {
    // 检查整列是否有效（没有悬空插头）
    return (mask & (mask >> 1)) === 0;
  }
}

---

2. 哈密尔顿回路

问题

• 在网格中找一条经过每个格子恰好一次的回路

function hamiltonianCircuit(m: number, n: number): bigint {
  // 状态：每行的连通分量编号
  // 用 4 进制表示：0=无插头，1,2,3=不同连通分量

  const dp: Map<number, bigint> = new Map();
  dp.set(0, BigInt(1));

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const newDp: Map<number, bigint> = new Map();

      for (const [state, cnt] of dp) {
        // 获取当前格子的左插头和上插头
        const left = (state >> ((n - j) * 2)) & 3;
        const up = (state >> ((n - j - 1) * 2)) & 3;

        // 转移逻辑
        if (left === 0 && up === 0) {
          // 方案1：横放+竖放形成回路起点
          // ...
        } else if (left !== 0 && up !== 0) {
          // 方案2：连接两个插头
          // ...
        } else {
          // 方案3：只有一个插头，延伸出去
          // ...
        }
      }

      dp.clear();
      for (const [k, v] of newDp) dp.set(k, v);
    }

    // 换行：去掉最低位（因为它已经移出棋盘）
    for (const [k, v] of dp) {
      dp.set(k >> 2, v);
    }
  }

  return dp.get(0) || Bigint(0);
}

---

3. 括号DP（更直观的插头表示）

问题

• 用 1×2 骨牌覆盖，骨牌形成括号匹配结构

function bracketDP(m: number, n: number): number {
  // 状态：4 进制
  // 0 = 无
  // 1 = 左插头
  // 2 = 右插头

  const dp: Map<number, bigint> = new Map();
  dp.set(0, Bigint(1));

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const newDp: Map<number, bigint> = new Map();

      for (const [state, cnt] of dp) {
        const left = (state >> ((n - j) * 2)) & 3;
        const up = (state >> ((n - j - 1) * 2)) & 3;

        if (left === 0 && up === 0) {
          // 新建一对括号
          const newState = state | (1 << ((n - j) * 2)) | (2 << ((n - j - 1) * 2));
          newDp.set(newState, (newDp.get(newState) || Bigint(0)) + cnt);
        } else if (left !== 0 && up !== 0) {
          // 配对括号
          if (left === 1 && up === 2) {
            // 左上配对
            const newState = state & ~(1 << ((n - j) * 2)) & ~(2 << ((n - j - 1) * 2));
            newDp.set(newState, (newDp.get(newState) || Bigint(0)) + cnt);
          }
          // 继续延伸...
        } else {
          // 延伸...
        }
      }

      dp.clear();
      for (const [k, v] of newDp) dp.set(k, v);
    }
  }

  return Number(dp.get(0) || Bigint(0));
}

---

复杂度分析

问题	状态数	转移数	复杂度
蒙德里安	O(2^n)	O(n)	O(m × 2^n)
哈密尔顿	O(n!?)	O(1)	巨大
括号匹配	O(3^n)	O(1)	O(mn × 3^n)

---

学习路径

1. 先掌握状态压缩 DP（旅行商）
2. 理解轮廓线概念
3. 理解插头连通性
4. 从简单问题开始（蒙德里安）
5. 进阶到哈密尔顿回路

---

参见: **DP算法索引** | **状态压缩DP**