每日算法 — 使用java实现轮廓线DP：状态压缩与插头转移求解棋盘覆盖问题

轮廓线DP（Profile DP）是状态压缩动态规划的高级形式，专门用于解决棋盘类覆盖问题，如骨牌覆盖、铺砖方案计数等。与普通状压DP逐行处理不同，轮廓线DP以”轮廓线”（当前行已处理格子的边界状态）作为状态，通过插头（即格子的连接方向）进行状态转移，大幅减少状态空间。本文用Java实现轮廓线DP求解经典问题——用1×2骨牌覆盖M×N棋盘，计算覆盖方案总数。

一、问题建模

给定一个M行N列的棋盘，用1×2的骨牌（可横放或竖放）不重叠地覆盖所有格子，求覆盖方案总数。

当M,N≤11时，普通状压DP的状态数为2^N，而轮廓线DP通过插头表示可将状态压缩至M+1位的三进制/四进制数，效率更高。

二、插头与轮廓线状态表示

轮廓线是已处理区域与未处理区域的分界线。对于每个轮廓线上的位置，用一个”插头”表示该位置是否与下方/右方格子连接：

• 0：无插头（该位置未与任何格子连接）
• 1：有插头（该位置已向上/左连接，等待右/下补齐）

以逐格处理为例，状态用M+1位的整数表示轮廓线上每个位置的插头类型。

package com.algorithm.profiledp;

import java.util.*;

/**
 * 轮廓线DP求解棋盘骨牌覆盖问题
 */
public class ProfileDPDomino {

    private final int rows;      // 棋盘行数
    private final int cols;      // 棋盘列数
    private final long[][] dp;   // dp[i][state] 表示处理到第i格、轮廓线状态为state的方案数

    public ProfileDPDomino(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        // 状态数最多为 2^(cols+1)，实际有效状态远少于此
        this.dp = new long[rows * cols + 1][1 << (cols + 1)];
    }

    /**
     * 获取状态s在第pos位的值（0或1）
     */
    private int getBit(int state, int pos) {
        return (state >> pos) & 1;
    }

    /**
     * 设置状态s在第pos位的值为val（0或1）
     */
    private int setBit(int state, int pos, int val) {
        if (val == 1) {
            return state | (1 << pos);
        } else {
            return state & ~(1 << pos);
        }
    }

    /**
     * 核心求解方法
     * 逐格处理棋盘，每个格子(i,j)有两种选择：
     * 1. 不放置骨牌（上方必须有插头补齐）
     * 2. 竖放骨牌（向下生成插头）
     * 3. 横放骨牌（向右生成插头）
     */
    public long solve() {
        int totalCells = rows * cols;
        int stateSize = 1 << (cols + 1);

        // 初始状态：没有任何插头
        dp[0][0] = 1;

        for (int cell = 0; cell < totalCells; cell++) {
            int row = cell / cols;
            int col = cell % cols;

            for (int state = 0; state < stateSize; state++) {
                if (dp[cell][state] == 0) continue;

                // 提取当前格子上方的插头（从上方延伸下来的）
                // 和左方的插头（从左方延伸过来的）
                int up = getBit(state, col);      // 上方插头（在轮廓线第col位）
                int left = getBit(state, cols);   // 左方插头（在轮廓线最后一位，即cols位）

                // 情况分析：
                // 当前格子(i,j)的处理方式取决于up和left

                if (up == 1 && left == 1) {
                    // 上方和左方都有插头，当前格子被覆盖，不生成新插头
                    // 清除上方和左方插头
                    int newState = setBit(state, col, 0);
                    newState = setBit(newState, cols, 0);
                    dp[cell + 1][newState] += dp[cell][state];
                } else if (up == 1 && left == 0) {
                    // 只有上方有插头，当前格子被上方骨牌覆盖
                    // 可以选择向右延伸（横放），或结束（不操作）
                    // 实际上上方有插头意味着上方骨牌占用了当前格子，当前格子已被覆盖
                    // 清除上方插头，左方插头保持0
                    int newState = setBit(state, col, 0);
                    newState = setBit(newState, cols, 0);
                    dp[cell + 1][newState] += dp[cell][state];
                } else if (up == 0 && left == 1) {
                    // 只有左方有插头，当前格子被左方骨牌覆盖
                    // 清除左方插头
                    int newState = setBit(state, col, 0);
                    newState = setBit(newState, cols, 0);
                    dp[cell + 1][newState] += dp[cell][state];
                } else {
                    // up == 0 && left == 0，当前格子空闲
                    // 必须放置一个骨牌覆盖它

                    // 选择1：竖放骨牌，向下生成插头（设置state的col位为1）
                    if (row + 1 < rows) {
                        int newState = setBit(state, col, 1);
                        newState = setBit(newState, cols, 0);
                        dp[cell + 1][newState] += dp[cell][state];
                    }

                    // 选择2：横放骨牌，向右生成插头（设置state的cols位为1）
                    if (col + 1 < cols) {
                        int newState = setBit(state, col, 0);
                        newState = setBit(newState, cols, 1);
                        dp[cell + 1][newState] += dp[cell][state];
                    }
                }
            }
        }

        // 最终状态应为全0（所有插头都被闭合）
        return dp[totalCells][0];
    }
}

三、优化版轮廓线DP（滚动数组）

package com.algorithm.profiledp;

import java.util.*;

/**
 * 优化版轮廓线DP：使用滚动数组+哈希表压缩状态
 * 适用于更大规模的棋盘
 */
public class OptimizedProfileDP {

    private final int rows;
    private final int cols;

    public OptimizedProfileDP(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
    }

    private int getBit(int state, int pos) {
        return (state >> pos) & 1;
    }

    private int setBit(int state, int pos, int val) {
        return val == 1 ? (state | (1 << pos)) : (state & ~(1 << pos));
    }

    public long solve() {
        // 使用两个Map交替作为当前层和下一层，只保存有效状态
        Map<Integer, Long> current = new HashMap<>();
        current.put(0, 1L);

        for (int cell = 0; cell < rows * cols; cell++) {
            int row = cell / cols;
            int col = cell % cols;
            Map<Integer, Long> next = new HashMap<>();

            for (Map.Entry<Integer, Long> entry : current.entrySet()) {
                int state = entry.getKey();
                long count = entry.getValue();
                int up = getBit(state, col);
                int left = getBit(state, cols);

                if (up == 1 && left == 1) {
                    // 被覆盖，清除两个插头
                    int ns = setBit(setBit(state, col, 0), cols, 0);
                    next.merge(ns, count, Long::sum);
                } else if (up == 1 && left == 0) {
                    int ns = setBit(setBit(state, col, 0), cols, 0);
                    next.merge(ns, count, Long::sum);
                } else if (up == 0 && left == 1) {
                    int ns = setBit(setBit(state, col, 0), cols, 0);
                    next.merge(ns, count, Long::sum);
                } else {
                    // 竖放：向下生成插头
                    if (row + 1 < rows) {
                        int ns = setBit(setBit(state, col, 1), cols, 0);
                        next.merge(ns, count, Long::sum);
                    }
                    // 横放：向右生成插头
                    if (col + 1 < cols) {
                        int ns = setBit(setBit(state, col, 0), cols, 1);
                        next.merge(ns, count, Long::sum);
                    }
                }
            }

            current = next;
        }

        return current.getOrDefault(0, 0L);
    }

    /**
     * 主测试方法
     */
    public static void main(String[] args) {
        System.out.println("轮廓线DP求解骨牌覆盖问题\n");

        int[][] testCases = {
            {2, 3}, {2, 4}, {3, 4}, {4, 4}, {4, 5}, {5, 6}
        };

        for (int[] tc : testCases) {
            int m = tc[0], n = tc[1];

            long start1 = System.nanoTime();
            ProfileDPDomino solver1 = new ProfileDPDomino(m, n);
            long ans1 = solver1.solve();
            long time1 = System.nanoTime() - start1;

            long start2 = System.nanoTime();
            OptimizedProfileDP solver2 = new OptimizedProfileDP(m, n);
            long ans2 = solver2.solve();
            long time2 = System.nanoTime() - start2;

            System.out.printf("%d×%d 棋盘: 方案数 = %d%n", m, n, ans1);
            System.out.printf("  基础版耗时: %.3f ms | 优化版耗时: %.3f ms%n%n",
                time1 / 1_000_000.0, time2 / 1_000_000.0);
        }
    }
}

四、扩展：插头DP求解多连方块覆盖

轮廓线DP的思想可以推广到更复杂的棋盘覆盖问题。以下展示如何用”括号表示法”的插头DP求解一般性连通块问题（如仓库管理员推箱子路径等）。

package com.algorithm.profiledp;

import java.util.*;

/**
 * 插头DP进阶：使用三进制/四进制状态表示多种插头类型
 * 求解带障碍物的棋盘覆盖问题
 */
public class AdvancedPlugDP {

    private final int rows;
    private final int cols;
    private final boolean[][] blocked; // true表示障碍物

    public AdvancedPlugDP(int rows, int cols, boolean[][] blocked) {
        this.rows = rows;
        this.cols = cols;
        this.blocked = blocked;
    }

    /**
     * 四进制状态表示：每个位置2位
     * 0: 无插头  1: 左插头  2: 上插头  3: 右插头（或下插头）
     */
    private int getQuad(int state, int pos) {
        return (state >> (pos * 2)) & 3;
    }

    private int setQuad(int state, int pos, int val) {
        int mask = ~(3 << (pos * 2));
        return (state & mask) | (val << (pos * 2));
    }

    public long solve() {
        Map<Integer, Long> current = new HashMap<>();
        current.put(0, 1L);

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                Map<Integer, Long> next = new HashMap<>();

                for (Map.Entry<Integer, Long> entry : current.entrySet()) {
                    int state = entry.getKey();
                    long count = entry.getValue();

                    if (blocked[r][c]) {
                        // 障碍物位置不能有插头
                        if (getQuad(state, c) == 0 && getQuad(state, c + 1) == 0) {
                            next.merge(state, count, Long::sum);
                        }
                        continue;
                    }

                    int up = getQuad(state, c);      // 来自上方的插头
                    int left = getQuad(state, c + 1); // 来自左方的插头（存储在c+1位）

                    // 根据up和left的组合进行状态转移
                    // 此框架可扩展为L型骨牌、T型骨牌等复杂覆盖
                    // 这里演示标准的1x2骨牌（用四进制简化编码）

                    if (up == 0 && left == 0) {
                        // 必须放置骨牌覆盖当前格子
                        // 竖放：设置上方插头为"下插头"（用2表示）
                        if (r + 1 < rows && !blocked[r + 1][c]) {
                            int ns = setQuad(state, c, 2);
                            ns = setQuad(ns, c + 1, 0);
                            next.merge(ns, count, Long::sum);
                        }
                        // 横放：设置左方插头为"右插头"（用3表示）
                        if (c + 1 < cols && !blocked[r][c + 1]) {
                            int ns = setQuad(state, c, 0);
                            ns = setQuad(ns, c + 1, 3);
                            next.merge(ns, count, Long::sum);
                        }
                    } else if (up != 0 && left == 0) {
                        // 上方有插头延伸下来，当前格子被覆盖
                        int ns = setQuad(setQuad(state, c, 0), c + 1, 0);
                        next.merge(ns, count, Long::sum);
                    } else if (up == 0 && left != 0) {
                        // 左方有插头延伸过来，当前格子被覆盖
                        int ns = setQuad(setQuad(state, c, 0), c + 1, 0);
                        next.merge(ns, count, Long::sum);
                    } else {
                        // 上方和左方都有插头，非法状态（格子被重复覆盖）
                        // 但在正确的1x2骨牌覆盖中不应出现
                    }
                }

                current = next;
            }

            // 行末：左方插头位(cols)应归零，此处简化处理
            // 实际实现需要更精细的状态管理
        }

        return current.getOrDefault(0, 0L);
    }
}

五、复杂度分析

其中S为有效状态数，实际远小于2^(C+1)。轮廓线DP相比普通状压DP的优势在于状态更紧凑，且天然支持逐格处理障碍物。

六、应用场景

轮廓线DP及插头DP的思想广泛应用于：
– 棋盘覆盖方案计数（骨牌、L型骨牌、多连方块）
– 网格路径问题（哈密顿回路、欧拉路径）
– 电路板布线（连通性约束下的最优路径）
– 推箱子等状态空间搜索问题的解数统计

掌握轮廓线DP的核心在于理解”轮廓线”作为已处理与未处理区域分界面的抽象，以及插头如何编码跨越该分界面的连接关系。