状压与计数 DP

动态规划 ⭐⭐⭐ 进阶 🔥 高频

💡 核心要点

状压 DP：用一个 n 位二进制整数表示集合，适用于 n ≤ 20、需要追踪"哪些元素已选"的场景，复杂度 O(2ⁿ × n²)
计数 DP：转移方程用 += 而非 max/min，初始化 dp[0] = 1；循环顺序决定计数的是组合数还是排列数
两者均是 DP 思想的延伸，掌握"状态定义 → 转移方程 → 初始化 → 答案提取"四步法同样适用

Part 1：状压 DP

识别信号

数据规模 n ≤ 20
题目需要追踪**"哪些元素已被选择/访问过"**
涉及全排列、哈密顿路径、集合划分等问题

通用思考框架

核心思想

用一个 n 位二进制整数（即 mask）表示一个集合：第 k 位为 1 表示元素 k 已被选入集合。

n 个元素共有种子集，恰好对应的整数 → 可直接作为 dp 数组的下标
这样就把"集合"这一复杂状态压缩成了一个整数，故称"状态压缩"

状态定义

形式	适用场景
`dp[mask]`	只需记录选了哪些元素（如子集划分）
`dp[mask][i]`	还需记录当前所在位置（如旅行商问题）

mask：已选元素的集合
i：当前所在的元素/节点编号

转移方程

枚举下一个要加入的元素 j（j 不在 mask 中）：

常用位运算速查表

操作	代码	含义
检查第 k 位	`(mask >> k) & 1`	元素 k 是否已选
设置第 k 位	`mask \| (1 << k)`	选入元素 k
清除第 k 位	`mask & ~(1 << k)`	移除元素 k
枚举子集	`for(int sub=mask; sub>0; sub=(sub-1)&mask)`	遍历 mask 的所有非空子集
统计 1 的个数	`Integer.bitCount(mask)`	已选元素个数

复杂度

状态数：
每个状态转移：
总复杂度：
n > 20 时不适用（状态数超过，加上转移后难以承受）

典型例题：最短 Hamilton 路径

题目描述：给定 n 个城市和任意两城市之间的距离，求从城市 0 出发、恰好经过每个城市一次后到达终点城市的最短路径长度。

状态定义

dp[mask][i]：已访问的城市集合为 mask，当前所在城市为 i 时，走过的最短距离。

转移方程

对每个未访问的城市 j（即第 j 位为 0）：

初始化与答案

初始化：dp[1][0] = 0（从城市 0 出发，mask = 0b...0001）
其余初始化为 Integer.MAX_VALUE / 2（防止加法溢出）
答案：min(dp[(1<<n)-1][i]) for all i（所有城市都访问过，枚举终点）

java

public int shortestHamiltonPath(int[][] dist) {
    int n = dist.length;
    int full = 1 << n;
    int[][] dp = new int[full][n];

    // 初始化为极大值
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0; // 从城市0出发

    for (int mask = 1; mask < full; mask++) {
        for (int i = 0; i < n; i++) {
            // 当前状态不合法：城市i不在mask中
            if (((mask >> i) & 1) == 0) continue;
            if (dp[mask][i] == Integer.MAX_VALUE / 2) continue;

            // 枚举下一个城市j
            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) == 1) continue; // j已在mask中
                int nextMask = mask | (1 << j);
                dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i][j]);
            }
        }
    }

    // 枚举终点，求最短路径
    int ans = Integer.MAX_VALUE;
    int allVisited = full - 1;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, dp[allVisited][i]);
    }
    return ans;
}

时间复杂度：，空间复杂度：

延伸题目

题目	链接	与典型题的区别	关键技巧
火柴拼正方形	LC 473	状态表示哪些火柴已用	需要剪枝优化，先排序大的
漂亮排列	LC 526	排列型状压	mask 表示已放置的数字集合

Part 2：计数 DP

识别信号

题目要求求方案数、组合数、构造方式的数量
关键词："有多少种方法"、"共有几种方案"、"不同的方式"

通用思考框架

与最优化 DP 的区别

对比项	最优化 DP	计数 DP
转移操作	`dp[i] = max/min(...)`	`dp[i] += dp[j]`
含义	当前状态的最优值	当前状态的方案数
初始化	通常为 0 或 ±∞	`dp[0] = 1`（空集/零容量算 1 种）

组合 vs 排列（关键区分）

这是计数 DP 中最容易混淆的知识点，循环顺序决定你计数的是组合还是排列：

循环顺序	计数类型	典型题
外层枚举物品，内层枚举容量	组合数（每种组合只计一次）	LC 518 零钱兑换 II
外层枚举容量，内层枚举物品	排列数（不同顺序分开计算）	LC 377 组合总和 IV

具体示例：硬币 [1, 2]，目标金额 3

组合数（外层物品）：{1,1,1}、{1,2} → 2 种
排列数（外层容量）：[1,1,1]、[1,2]、[2,1] → 3 种

为什么？

外层枚举物品时，硬币 2 只在处理"物品 2"时才被考虑，{1,2} 和 {2,1} 对应的状态是同一个，不会重复计入
外层枚举容量时，每个容量值都会重新枚举所有物品，[1,2] 和 [2,1] 对应不同的转移路径，会分别计入

初始化

dp[0] = 1：空集或零容量视为"恰好 1 种方案"，这是递推的起点。

典型例题：不同的二叉搜索树 LeetCode 96

题目描述：给定整数 n，求以 1 到 n 为节点构成的结构不同的二叉搜索树共有多少种。

状态定义

dp[n]：由 n 个节点构成的不同 BST 的数量。

关键洞察

枚举根节点 k（k 从 1 到 n）：

左子树由 1..k-1 共 k-1 个节点构成，有 dp[k-1] 种
右子树由 k+1..n 共 n-k 个节点构成，有 dp[n-k] 种
左右子树独立，方案数相乘

这正是卡特兰数（Catalan Number）的递推公式，其闭合公式为：

初始化与答案

dp[0] = 1（空树算 1 种）
dp[1] = 1（单节点树 1 种）
答案：dp[n]

java

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1; // 空树算1种（递推起点）
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        for (int k = 1; k <= i; k++) {
            // 以k为根：左子树k-1个节点，右子树i-k个节点
            dp[i] += dp[k - 1] * dp[i - k];
        }
    }

    return dp[n];
}

时间复杂度：，空间复杂度：

结果为卡特兰数：1, 1, 2, 5, 14, 42, 132, ...（n = 0, 1, 2, 3, 4, 5, 6, ...）

延伸题目

题目	链接	与典型题的区别	关键技巧
完全平方数	LC 279	完全背包求最小值	也可用 BFS
组合总和 IV	LC 377	排列型计数	外层容量内层物品，与 LC 518 对比
整数拆分	LC 343	枚举第一刀位置	`max(j(i-j), jdp[i-j])`

常见陷阱与调试

状压 DP 陷阱

整数溢出：初始化时用 Integer.MAX_VALUE / 2 而非 Integer.MAX_VALUE，避免加法后溢出为负数
状态合法性检查：转移前务必检查 ((mask >> i) & 1) == 1，确认当前位置 i 确实在 mask 中
下标从 0 还是从 1：dp[1][0] = 0 中的 1 是 0b0001（城市 0 已访问），不要与城市编号混淆
枚举子集的边界：for(int sub = mask; sub > 0; sub = (sub-1) & mask) 不包含空集；若需要空集，循环条件改为 sub >= 0 并在 sub == 0 后 break

计数 DP 陷阱

忘记初始化 dp[0] = 1：这是所有计数 DP 的递推起点，遗漏会导致所有结果为 0
组合/排列混淆：先确定题目要求的是组合数还是排列数，再决定循环顺序
溢出问题：方案数可能非常大，注意题目是否要求取模（% 1_000_000_007）
重复计数：如果枚举时没有限制顺序（如排列数），确认这是题目期望的行为，否则需要调整循环顺序

状压与计数 DP ​

Part 1：状压 DP ​

识别信号 ​

通用思考框架 ​

核心思想 ​

状态定义 ​

转移方程 ​

常用位运算速查表 ​

复杂度 ​

典型例题：最短 Hamilton 路径 ​

状态定义 ​

转移方程 ​

初始化与答案 ​

延伸题目 ​

Part 2：计数 DP ​

识别信号 ​

通用思考框架 ​

与最优化 DP 的区别 ​

组合 vs 排列（关键区分） ​

初始化 ​

典型例题：不同的二叉搜索树 LeetCode 96 ​

状态定义 ​

关键洞察 ​

初始化与答案 ​

延伸题目 ​

常见陷阱与调试 ​

状压与计数 DP

Part 1：状压 DP

识别信号

通用思考框架

核心思想

状态定义

转移方程

常用位运算速查表

复杂度

典型例题：最短 Hamilton 路径

状态定义

转移方程

初始化与答案

延伸题目

Part 2：计数 DP

识别信号

通用思考框架

与最优化 DP 的区别

组合 vs 排列（关键区分）

初始化

典型例题：不同的二叉搜索树 LeetCode 96

状态定义

关键洞察

初始化与答案

延伸题目

常见陷阱与调试