狀壓DP-基本框架

- 一、狀壓DP的核心思想與適用場景
- - 1.1 問題特征
  - 1.2 核心思想
  - 1.3 與傳統DP的對比
- 二、位運算基礎：狀壓DP的語法
- 三、狀壓DP的基本框架
- - 3.1 步驟拆解
  - 3.2 通用代碼模板
- 四、經典案例詳解
- - 4.1 旅行商問題（TSP）
  - - 問題描述
    - 狀壓DP設計
    - 代碼實現
  - 4.2 集合覆蓋問題（最小代價覆蓋所有元素）
  - - 問題描述
    - 狀壓DP設計
    - 代碼實現
- 五、狀壓DP的優化技巧
- - 5.1 狀態剪枝
  - 5.2 位運算優化
  - 5.3 空間優化
  - 總結

狀態壓縮動態規劃（Bitmask DP）是解決“小規模集合選擇”問題的高效方法，當問題涉及對有限元素的子集進行狀態描述時，傳統DP的多維狀態會導致空間爆炸，而狀壓DP通過二進制位表示集合狀態，將高維狀態壓縮為一個整數，顯著降低空間復雜度。

一、狀壓DP的核心思想與適用場景

1.1 問題特征

狀壓DP適用于以下場景：

元素數量少：通常n≤20（二進制狀態需要2^n個，n=20對應約百萬級狀態，可接受）。
狀態與子集相關：問題的解依賴于“哪些元素被選中”或“元素的選擇順序”（如旅行商問題中已訪問的城市集合）。
子集狀態可轉移：從一個子集狀態可通過添加/刪除元素過渡到另一個狀態（如從“選中{0,1}”到“選中{0,1,2}”）。

1.2 核心思想

狀態壓縮：用一個整數（二進制數）表示元素的選擇狀態。例如，n=3時：
- 二進制101（十進制5）表示選中第0和第2個元素（從右往左數，低位對應下標0）；
- 二進制000表示未選中任何元素。
DP狀態定義：dp[mask]表示“在狀態mask下的最優解”（如最小代價、最大價值等），其中mask是壓縮后的二進制狀態。
狀態轉移：通過枚舉mask中未選中的元素，生成新狀態mask | (1 << i)，并更新dp[new_mask]。

1.3 與傳統DP的對比

維度	傳統DP（如背包問題）	狀壓DP
狀態表示	多維數組（如`dp[i][j]`）	單整數`mask`（壓縮子集）
適用規模	元素數量大（`n≤1e5`）	元素數量小（`n≤20`）
核心技巧	空間優化（如滾動數組）	位運算操作（狀態轉換）
典型問題	0/1背包、最長上升子序列	旅行商問題、集合覆蓋問題

二、位運算基礎：狀壓DP的語法

狀壓DP依賴二進制位運算實現狀態操作，核心運算如下：

操作	含義	位運算表達式
檢查元素`i`是否選中	第`i`位是否為1	`(mask & (1 << i)) != 0`
選中元素`i`	將第`i`位設為1	`mask
取消選中元素`i`	將第`i`位設為0	`mask & ~(1 << i)`
切換元素`i`的狀態	第`i`位0變1，1變0	`mask ^ (1 << i)`
統計選中元素數量	二進制中1的個數（popcount）	`Integer.bitCount(mask)`
清空所有元素	狀態置為0	`mask = 0`

示例：mask = 5（二進制101）：

檢查元素1是否選中：5 & (1<<1) = 101 & 010 = 000 → 未選中；
選中元素1：5 | (1<<1) = 101 | 010 = 111 → 新狀態7；
統計選中數量：Integer.bitCount(5) = 2。

三、狀壓DP的基本框架

3.1 步驟拆解

確定狀態表示：用mask表示元素的選擇狀態，定義dp[mask]的具體含義（如代價、價值）。
初始化：設置初始狀態的dp值（如dp[0] = 0表示未選任何元素時的初始代價）。
狀態轉移：
- 遍歷所有可能的mask（從0到2^n - 1）；
- 對每個mask，枚舉可添加的元素i（未被mask選中）；
- 計算新狀態new_mask = mask | (1 << i)，更新dp[new_mask]。
結果提取：根據問題目標，返回dp[full_mask]（full_mask = (1 << n) - 1表示所有元素都被選中）或其他特定狀態的值。

3.2 通用代碼模板

public class BitmaskDPTemplate {int n; // 元素數量int[] dp; // dp[mask]表示狀態mask下的最優解public BitmaskDPTemplate(int n) {this.n = n;int size = 1 << n; // 狀態總數：2^ndp = new int[size];// 初始化：除初始狀態外均設為無窮大（求最小值時）或負無窮（求最大值時）Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0; // 初始狀態：未選任何元素}public int solve() {int fullMask = (1 << n) - 1; // 所有元素都被選中的狀態// 遍歷所有狀態for (int mask = 0; mask < (1 << n); mask++) {if (dp[mask] == Integer.MAX_VALUE) continue; // 跳過不可達狀態// 枚舉可添加的元素ifor (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) continue; // 元素i已被選中，跳過int newMask = mask | (1 << i); // 選中元素i后的新狀態// 計算新狀態的代價（根據具體問題修改）int cost = calculateCost(mask, i);dp[newMask] = Math.min(dp[newMask], dp[mask] + cost);}}return dp[fullMask]; // 返回所有元素被選中時的最優解}// 根據具體問題計算從mask添加元素i的代價private int calculateCost(int mask, int i) {// 示例：代價為i+1（實際需根據問題定義）return i + 1;}public static void main(String[] args) {BitmaskDPTemplate solver = new BitmaskDPTemplate(3); // 3個元素System.out.println(solver.solve()); // 輸出0+1+2+3=6（示例邏輯）}
}

四、經典案例詳解

4.1 旅行商問題（TSP）

問題描述

給定n個城市和兩兩之間的距離，求從起點出發，訪問所有城市恰好一次并返回起點的最短路徑。

示例：n=4，距離矩陣dist[i][j]表示城市i到j的距離，求最短回路。

狀壓DP設計

狀態定義：dp[mask][u]表示“已訪問的城市集合為mask，當前在城市u時的最短距離”。
（注：此處狀態包含mask和當前城市u，是二維狀壓DP）
狀態轉移：
- 初始狀態：dp[1 << start][start] = 0（僅訪問起點，距離為0）。
- 對每個mask和當前城市u，枚舉未訪問的城市v，則：
  dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])。
結果計算：訪問所有城市后返回起點，總距離為min(dp[full_mask][u] + dist[u][start])（u為最后一個城市）。

代碼實現

import java.util.*;public class TSP {int n;int[][] dist; // 距離矩陣int[][] dp; // dp[mask][u]: 狀態mask下當前在u的最短距離final int INF = 1 << 30;public TSP(int n, int[][] dist) {this.n = n;this.dist = dist;int size = 1 << n;dp = new int[size][n];// 初始化：所有狀態設為無窮大for (int i = 0; i < size; i++) {Arrays.fill(dp[i], INF);}// 起點設為0，初始狀態：僅訪問0dp[1 << 0][0] = 0;}public int shortestPath() {int fullMask = (1 << n) - 1;// 遍歷所有狀態for (int mask = 0; mask < (1 << n); mask++) {// 遍歷當前所在城市ufor (int u = 0; u < n; u++) {if ((mask & (1 << u)) == 0) continue; // u不在mask中，跳過if (dp[mask][u] == INF) continue; // 狀態不可達// 枚舉未訪問的城市vfor (int v = 0; v < n; v++) {if ((mask & (1 << v)) != 0) continue; // v已訪問，跳過int newMask = mask | (1 << v);// 更新新狀態的距離if (dp[newMask][v] > dp[mask][u] + dist[u][v]) {dp[newMask][v] = dp[mask][u] + dist[u][v];}}}}// 計算返回起點的總距離int result = INF;for (int u = 0; u < n; u++) {if (u == 0) continue; // 起點無需返回result = Math.min(result, dp[fullMask][u] + dist[u][0]);}return result;}public static void main(String[] args) {// 示例：4個城市的距離矩陣int n = 4;int[][] dist = {{0, 1, 2, 3},{1, 0, 4, 5},{2, 4, 0, 6},{3, 5, 6, 0}};TSP tsp = new TSP(n, dist);System.out.println(tsp.shortestPath()); // 輸出1+4+6+3=14（示例路徑：0→1→2→3→0）}
}

4.2 集合覆蓋問題（最小代價覆蓋所有元素）

問題描述

給定n個元素和m個子集，每個子集S_i有代價c_i，求代價最小的子集組合，使其覆蓋所有n個元素。

示例：n=3，子集S_0={0,1}（代價2），S_1={1,2}（代價3），S_2={0,2}（代價4），最優解為S_0 + S_1（代價5，覆蓋{0,1,2}）。

狀壓DP設計

狀態定義：dp[mask]表示“覆蓋元素集合為mask時的最小代價”。
狀態轉移：
- 初始狀態：dp[0] = 0（覆蓋空集代價0）。
- 對每個mask和每個子集S_i，新覆蓋的集合為new_mask = mask | S_i_mask（S_i_mask是子集S_i的二進制表示），則：
  dp[new_mask] = min(dp[new_mask], dp[mask] + c_i)。
結果提取：dp[full_mask]（full_mask = (1 << n) - 1）。

代碼實現

import java.util.*;public class SetCover {int n; // 元素總數int m; // 子集數量int[] subsetMask; // 每個子集的二進制表示int[] cost; // 每個子集的代價int[] dp; // dp[mask]: 覆蓋mask集合的最小代價final int INF = 1 << 30;public SetCover(int n, int m, int[] subsetMask, int[] cost) {this.n = n;this.m = m;this.subsetMask = subsetMask;this.cost = cost;int size = 1 << n;dp = new int[size];Arrays.fill(dp, INF);dp[0] = 0; // 初始狀態}public int minTotalCost() {int fullMask = (1 << n) - 1;// 遍歷所有狀態for (int mask = 0; mask < (1 << n); mask++) {if (dp[mask] == INF) continue;// 枚舉每個子集for (int i = 0; i < m; i++) {int newMask = mask | subsetMask[i];// 更新新狀態的代價if (dp[newMask] > dp[mask] + cost[i]) {dp[newMask] = dp[mask] + cost[i];}}}return dp[fullMask];}public static void main(String[] args) {int n = 3; // 元素0,1,2int m = 3; // 3個子集int[] subsetMask = {0b110, // S0: {1,2}（二進制從右數，0b110表示第1和2位為1）0b101, // S1: {0,2}0b011  // S2: {0,1}};int[] cost = {2, 3, 4};SetCover solver = new SetCover(n, m, subsetMask, cost);System.out.println(solver.minTotalCost()); // 輸出2+3=5（S0覆蓋1,2，S1覆蓋0）}
}