位元遮罩 DP（狀態壓縮）

Dynamic Programming & RecursionPriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowing 更新於 Sep 19, 2026
Section priorityPriority 5 of 5 — Must know — expect it in almost every loopMust knowPriority 4 of 5 — High value — a gap here costs you roundsHigh valuePriority 3 of 5 — Worth knowing — usually a variant of a must-know patternWorth knowingPriority 2 of 5 — Niche — read once, revisit only if a company is known to askNicheMarked on the sections that carry it — unmarked sections are background/reference.

範圍 — 狀態是「一個用整數編碼的子集合」的 DP：遮罩運算、子遮罩列舉、TSP 與指派問題的模板，以及 n <= 20 這條規模上限。 另見：dp.md — 精簡版的位元遮罩模板，以及它在各 DP 模式中的定位；bit_manipulation.md — 純粹的位元技巧，不談 DP。

LeetCode 題目清單

概觀

關鍵性質

  • 複雜度：標準的子集合 DP 是 O(2^n * n) 時間、O(2^n) 空間 — 所以 n <= 20 是實務上的 天花板（2^20 ≈ 1e6）。子遮罩列舉的成本是 O(3^n)。
  • 核心想法：DP 的狀態是一個集合，而 n 個元素的集合就只是一個 n 位元的整數， 所以整張 memo 表就是一個以該整數為索引的一維陣列。
  • 什麼時候用：題目要記錄「我已經用過／走過哪些元素」、n 很小，而且暴力解會是一個排列搜尋。

參考資料

模板與演算法

狀態壓縮模式

什麼時候該用位元遮罩 DP：

  • 狀態空間很小（≤ 20 個元素）
  • 需要記錄哪些元素被選了／走過了
  • 排列／組合類的問題
  • 旅行推銷員問題的各種變形

常見的位元遮罩運算：

python
# python
# IDEA: the bit vocabulary every bitmask DP is written in
# Check if i-th bit is set
if mask & (1 << i):
    pass

# Set i-th bit
new_mask = mask | (1 << i)

# Unset i-th bit
new_mask = mask & ~(1 << i)

# Iterate through all submasks
submask = mask
while submask:
    # Process submask
    submask = (submask - 1) & mask

Java 的位元遮罩運算：

java
// java
// IDEA: the same bit vocabulary in Java
// Check if i-th bit is set
if ((mask & (1 << i)) != 0) {
    // i-th item is included
}

// Set i-th bit
int newMask = mask | (1 << i);

// Unset i-th bit
int newMask = mask & ~(1 << i);

// Toggle i-th bit
int newMask = mask ^ (1 << i);

// Count number of set bits
int count = Integer.bitCount(mask);

// Get lowest set bit
int lowestBit = mask & (-mask);

// Iterate through all subsets
for (int mask = 0; mask < (1 << n); mask++) {
    // Process mask
}

// Iterate through all submasks of mask
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
    // Process submask
}

模式 1：走遍所有節點（TSP 變形）

題型：找出恰好走過所有節點一次的最短路徑

狀態定義：dp[mask][i] = 走完 mask 中所有節點、且停在節點 i 的最小成本

轉移：對每個還沒走過的節點 j，試著從目前的節點 i 走過去

時間複雜度：O(2^n × n²) 空間複雜度：O(2^n × n)

範例：LC 847 - Shortest Path Visiting All Nodes

java
// java
// LC 847 - Shortest Path Visiting All Nodes
// IDEA: BFS over (mask, node); dp[mask][node] = fewest edges to stand on `node`
//       having visited exactly the set `mask`
// time = O(2^n * n^2), space = O(2^n * n)
public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int[][] dp = new int[1 << n][n];
    // NOTE !!! every state must start at +inf, not 0 — otherwise
    // `dp[nextMask][next] > dist + 1` is false for unvisited states and the BFS never expands
    for (int[] row : dp) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }
    Queue<int[]> queue = new LinkedList<>();

    // Initialize: start from any node
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 0;
        queue.offer(new int[]{1 << i, i});
    }

    int target = (1 << n) - 1;

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int mask = curr[0], node = curr[1];
        int dist = dp[mask][node];

        if (mask == target) {
            return dist;
        }

        for (int next : graph[node]) {
            int nextMask = mask | (1 << next);
            if (dp[nextMask][next] > dist + 1) {
                dp[nextMask][next] = dist + 1;
                queue.offer(new int[]{nextMask, next});
            }
        }
    }

    return -1;
}

模式 2：指派問題

題型：把 n 件工作指派給 n 個工人，讓總成本最小／最大

狀態定義：dp[w][mask] = 在恰好 w 個工人接下 mask 這些工作時的最小完工時間

轉移：讓工人 w 接下 mask 的某個子遮罩；剩下的交給工人 1..w-1

時間複雜度：O(k × 3^n) — 對所有遮罩跑子遮罩迴圈是 3^n，每個工人各跑一次 空間複雜度：O(k × 2^n)

工人數必須是狀態的一部分。 只用 dp[mask] 去最小化 max(dp[mask ^ sub], sum(sub))， 等於是把 mask 拆成不限數量的組別，那算出來的是「工人愛用幾個就用幾個時的最小完工時間」， 而不是「恰好用 k 個」。

範例：LC 1723 - Find Minimum Time to Finish All Jobs

java
// java
// LC 1723 - Find Minimum Time to Finish All Jobs
// IDEA: dp[w][mask] = min makespan after w workers have taken exactly the jobs in mask
// time = O(k * 3^n), space = O(k * 2^n)
public int minimumTimeRequired(int[] jobs, int k) {
    int n = jobs.length, full = (1 << n) - 1;

    // Precompute sum for each subset (lowest-set-bit recurrence, O(2^n))
    int[] subsetSum = new int[1 << n];
    for (int mask = 1; mask <= full; mask++) {
        int lowBit = mask & -mask;
        subsetSum[mask] = subsetSum[mask ^ lowBit] + jobs[Integer.numberOfTrailingZeros(lowBit)];
    }

    int[][] dp = new int[k + 1][1 << n];
    for (int[] row : dp) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }
    dp[0][0] = 0;                       // 0 workers can only cover the empty job set

    for (int w = 1; w <= k; w++) {
        for (int mask = 0; mask <= full; mask++) {
            // NOTE !!! `sub` is worker w's share; `mask ^ sub` goes to workers 1..w-1
            for (int sub = mask; ; sub = (sub - 1) & mask) {
                int prev = dp[w - 1][mask ^ sub];
                if (prev != Integer.MAX_VALUE) {
                    dp[w][mask] = Math.min(dp[w][mask], Math.max(prev, subsetSum[sub]));
                }
                if (sub == 0) break;    // must run sub == 0 too (worker w idles), then stop
            }
        }
    }

    return dp[k][full];
}

模式 3：帶限制的子集合選取

題型：選出滿足特定限制的子集合

狀態定義：dp[mask] = 達成 mask 所代表狀態的方法數／最小成本

轉移：對每個元素，依照目前的遮罩決定要不要納入

時間複雜度：O(2^n × n)，或用子遮罩列舉時是 O(3^n) 空間複雜度：O(2^n)

範例：LC 691 - Stickers to Spell Word

java
// java
// LC 691 - Stickers to Spell Word
// IDEA: dp[mask] = fewest stickers to cover the letters in `mask`
// time = O(2^n * stickers * n), space = O(2^n)
public int minStickers(String[] stickers, String target) {
    int n = target.length();
    int[] dp = new int[1 << n];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;

        for (String sticker : stickers) {
            int newMask = mask;
            int[] counts = new int[26];

            for (char c : sticker.toCharArray()) {
                counts[c - 'a']++;
            }

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    char c = target.charAt(i);
                    if (counts[c - 'a'] > 0) {
                        counts[c - 'a']--;
                        newMask |= (1 << i);
                    }
                }
            }

            if (dp[newMask] == -1 || dp[newMask] > dp[mask] + 1) {
                dp[newMask] = dp[mask] + 1;
            }
        }
    }

    return dp[(1 << n) - 1];
}

模式 4：分割成 K 個子集合

題型：把 n 個元素在限制下分成 k 組

狀態定義：dp[mask] = mask 裡的元素能不能剛好切成幾個完整的組

轉移：試著從目前的狀態湊出一個完整的組

時間複雜度：O(2^n × n) 空間複雜度：O(2^n)

範例：LC 698 - Partition to K Equal Sum Subsets

java
// java
// LC 698 - Partition to K Equal Sum Subsets
// IDEA: fill one bucket at a time; dp[mask] tracks the running remainder
// time = O(2^n * n), space = O(2^n)
public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int num : nums) sum += num;

    if (sum % k != 0) return false;

    int target = sum / k;
    int n = nums.length;
    boolean[] dp = new boolean[1 << n];
    int[] total = new int[1 << n];
    dp[0] = true;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) continue;

            int newMask = mask | (1 << i);

            if (total[mask] % target + nums[i] <= target) {
                dp[newMask] = true;
                total[newMask] = total[mask] + nums[i];
            }
        }
    }

    return dp[(1 << n) - 1];
}

Pattern 5: Set Cover — the mask is the GOAL, not the items Priority 5 of 5 — Must know — expect it in almost every loop

Problem Type: pick the fewest items so that the union of what they cover is everything

State Definition: dp[cover] = the cheapest team whose skills union to exactly cover

Transition: for each person p, dp[cover | skills(p)] <- dp[cover] + {p}

Time Complexity: O(people × 2^m) Space Complexity: O(2^m) states (plus whatever you store per state to rebuild the answer)

The mask indexes the SKILLS, not the PEOPLE. This is the whole trick and it is the one thing that goes wrong in the room. LC 1125 has up to 60 people and at most 16 skills — 2^60 is impossible and 2^16 is nothing. Whenever n looks far too big for bitmask DP, check whether the requirement is the small side.

Example: LC 1125 - Smallest Sufficient Team

java
// java
// LC 1125 - Smallest Sufficient Team
// IDEA: dp[cover] = smallest team covering that skill set. People are up to 60, so the
//       team itself is stored as a 64-bit person mask and rebuilt by scanning its bits.
// time = O(people * 2^m), space = O(2^m)
public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
    int m = reqSkills.length, full = (1 << m) - 1;
    Map<String, Integer> skillId = new HashMap<>();
    for (int i = 0; i < m; i++) skillId.put(reqSkills[i], i);

    long[] team = new long[1 << m];             // team[cover] = bitmask of chosen people
    int[] size = new int[1 << m];
    Arrays.fill(size, Integer.MAX_VALUE);
    size[0] = 0;                                // the empty team covers nothing, for free

    for (int p = 0; p < people.size(); p++) {
        int pm = 0;
        for (String s : people.get(p)) {
            Integer id = skillId.get(s);        // people may list skills nobody asked for
            if (id != null) pm |= 1 << id;
        }
        if (pm == 0) continue;
        for (int cover = 0; cover <= full; cover++) {
            if (size[cover] == Integer.MAX_VALUE) continue;
            int next = cover | pm;
            /** NOTE !!! `next >= cover` always, and when pm is already inside `cover` we get
             *  next == cover and the relaxation below is a no-op — so a person can never be
             *  added twice even though we write forward into the same array. */
            if (size[next] > size[cover] + 1) {
                size[next] = size[cover] + 1;
                team[next] = team[cover] | (1L << p);
            }
        }
    }

    long chosen = team[full];
    int[] ans = new int[size[full]];
    int k = 0;
    for (int p = 0; p < people.size(); p++) {
        if ((chosen >> p & 1) == 1) ans[k++] = p;
    }
    return ans;
}
python
# python
# LC 1125 - Smallest Sufficient Team
# IDEA: dict from skill-cover mask -> the smallest team reaching it. Only reachable
#       covers are ever stored, which in practice is far fewer than 2^m.
# time = O(people * 2^m), space = O(2^m * m)
def smallestSufficientTeam(req_skills, people):
    skill_id = {s: i for i, s in enumerate(req_skills)}
    full = (1 << len(req_skills)) - 1

    dp = {0: []}                                   # cover -> list of person indices
    for p, skills in enumerate(people):
        pm = 0
        for s in skills:
            if s in skill_id:                      # ignore skills nobody required
                pm |= 1 << skill_id[s]
        if pm == 0:
            continue
        # NOTE !!! iterate a SNAPSHOT -- otherwise person p can be re-used within one pass
        for cover, crew in list(dp.items()):
            nxt = cover | pm
            if nxt == cover:
                continue
            if nxt not in dp or len(dp[nxt]) > len(crew) + 1:
                dp[nxt] = crew + [p]

    return dp[full]

Similar problems: LC 691 Stickers to Spell Word (same shape, but a sticker may be used more than once, so relax dp[cover] from every cover repeatedly — BFS or an ascending sweep), LC 1434 Number of Ways to Wear Different Hats, LC 2305 Fair Distribution of Cookies.

Pattern 6: Row-by-Row Profile DP — the mask is ONE ROW Priority 4 of 5 — High value — a gap here costs you rounds

Problem Type: fill a grid subject to constraints between a cell and its neighbours, where the grid is narrow (cols <= ~12) but may be arbitrarily tall

State Definition: dp[i][mask] = best value for rows 0..i when row i is exactly mask

Transition: for each pair (prev, cur) of legal row layouts, check the cross-row rule

Time Complexity: O(rows × 4^cols) naive, O(rows × 3^cols) if you enumerate submasks Space Complexity: O(2^cols) — only the previous row is needed

Which dimension goes in the mask. Always the short one. LC 1349 is m <= 8 rows by n <= 8 columns, but the same problem with 10,000 rows and 8 columns is identical work — the exponent is on the width alone. Transpose first if the grid is tall and thin the other way.

The constraints split cleanly into two independent checks, and keeping them separate is what makes this writable under pressure:

text
within a row   :  no two students side by side  ->  mask & (mask << 1) == 0
                  no student on a broken seat   ->  mask & broken[i]   == 0

across rows    :  no upper-left neighbour       ->  cur & (prev << 1)  == 0
                  no upper-right neighbour      ->  cur & (prev >> 1)  == 0
                  (directly above is ALLOWED — cheating needs a diagonal)

Example: LC 1349 - Maximum Students Taking Exam

java
// java
// LC 1349 - Maximum Students Taking Exam
// IDEA: dp[mask] = most students seated so far with the current row laid out as `mask`.
//       Row validity and cross-row validity are two separate bit tests.
// time = O(m * 4^n), space = O(2^n)
public int maxStudents(char[][] seats) {
    int m = seats.length, n = seats[0].length, full = 1 << n;

    int[] broken = new int[m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (seats[i][j] == '#') broken[i] |= 1 << j;
        }
    }

    int[] prev = new int[full];
    Arrays.fill(prev, -1);
    prev[0] = 0;                                  // before row 0: only the empty layout exists

    for (int i = 0; i < m; i++) {
        int[] cur = new int[full];
        Arrays.fill(cur, -1);
        for (int mask = 0; mask < full; mask++) {
            if ((mask & broken[i]) != 0) continue;         // sits on a broken seat
            if ((mask & (mask << 1)) != 0) continue;       // two students side by side
            for (int p = 0; p < full; p++) {
                if (prev[p] == -1) continue;               // unreachable previous layout
                if ((mask & (p << 1)) != 0) continue;      // upper-left neighbour
                if ((mask & (p >> 1)) != 0) continue;      // upper-right neighbour
                cur[mask] = Math.max(cur[mask], prev[p] + Integer.bitCount(mask));
            }
        }
        prev = cur;
    }

    int best = 0;
    for (int v : prev) best = Math.max(best, v);
    return best;
}
python
# python
# LC 1349 - Maximum Students Taking Exam
# IDEA: same two-tier validity test; -1 marks an unreachable layout so it can never
#       be relaxed from (a plain 0 default would invent seatings that do not exist)
# time = O(m * 4^n), space = O(2^n)
def maxStudents(seats):
    m, n = len(seats), len(seats[0])
    full = 1 << n

    broken = [0] * m
    for i in range(m):
        for j in range(n):
            if seats[i][j] == '#':
                broken[i] |= 1 << j

    prev = [-1] * full
    prev[0] = 0
    for i in range(m):
        cur = [-1] * full
        for mask in range(full):
            if mask & broken[i] or mask & (mask << 1):
                continue
            best = max((prev[p] for p in range(full)
                        if prev[p] >= 0 and not (mask & (p << 1)) and not (mask & (p >> 1))),
                       default=-1)
            if best >= 0:
                cur[mask] = best + bin(mask).count('1')
        prev = cur

    return max(prev)

Similar problems: LC 1659 Maximize Grid Happiness (profile DP with three states per cell, so base 3 instead of base 2), LC 1655 Distribute Repeating Integers, and the classic domino/tromino tiling family, where the mask describes which cells of the next row are already covered.

Bitmask DP Common Patterns Summary

Pattern State Definition Transition Example Problems
Visit All Nodes dp[mask][i] = cost to visit mask, end at i Try next unvisited node LC 847, LC 943
Assignment dp[mask] = cost to assign tasks in mask Assign next task to worker LC 1723, LC 1986
Subset Selection dp[mask] = ways/cost for subset mask Include/exclude next item LC 691, LC 1434
Partition dp[mask] = can partition mask into groups Form complete groups LC 698, LC 1681
Set Cover dp[cover] = cheapest set of items reaching that cover Union in one more item LC 1125, LC 691
Profile DP dp[i][mask] = state at row i with column mask Process row by row LC 1349, tiling problems

進階技巧

1. 預先算好子集合的性質：

java
// java
// IDEA: subset-sum precompute via the lowest set bit
// time = O(2^n), space = O(2^n)
// Precompute sum for all subsets - O(2^n × n)
int[] subsetSum = new int[1 << n];
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            subsetSum[mask] += arr[i];
        }
    }
}

2. 子遮罩列舉 — O(3^n)：

java
// java
// IDEA: submask enumeration — the `(sub - 1) & mask` idiom
// time = O(3^n), space = O(1)
// For each mask, iterate through all its submasks
for (int mask = 0; mask < (1 << n); mask++) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // dp[mask] can be computed from dp[submask] and dp[mask ^ submask]
        dp[mask] = Math.min(dp[mask], dp[submask] + dp[mask ^ submask]);
    }
}

3. SOS（Sum Over Subsets）DP — O(2^n × n)：

java
// java
// IDEA: SOS (sum over subsets) DP — n passes instead of 3^n
// time = O(2^n * n), space = O(2^n)
// For each mask, sum values of all its submasks
int[] dp = new int[1 << n];
// ... initialize dp ...

for (int i = 0; i < n; i++) {
    for (int mask = 0; mask < (1 << n); mask++) {
        if ((mask & (1 << i)) != 0) {
            dp[mask] += dp[mask ^ (1 << i)];
        }
    }
}

複雜度分析

技巧 時間複雜度 空間複雜度 適用情境
基本位元遮罩 O(2^n × n) O(2^n) 走遍全部、指派
子遮罩列舉 O(3^n) O(2^n) 分割、子集合和
SOS DP O(2^n × n) O(2^n) 子集合求和
輪廓線 DP O(2^m × n) O(2^m) 網格鋪磚（m = 寬度）

可行規模的界線：

  • n ≤ 15：非常安全，約 32K 個狀態
  • n ≤ 20：可行，約 1M 個狀態
  • n ≤ 24：很吃緊，約 16M 個狀態（小心 TLE）
  • n > 24：通常已經超出位元遮罩 DP 能處理的範圍

面試提示

  1. 認出狀態壓縮：

    • 關鍵字：「走遍全部」、「指派」、「分成 k 組」
    • 限制條件：n ≤ 20
    • 需要記錄子集合／走過的元素

  2. 選對狀態：

    • TSP 型：dp[mask][last_node]
    • 指派型：dp[mask]（隱含地派給第 k 個工人）
    • 分割型：dp[mask] 搭配取模檢查

  3. 最佳化：

    • 預先算好子集合的性質
    • 最短路徑類的問題改用 BFS
    • 子集合求和的查詢考慮用 SOS DP

  4. 常見錯誤：

    • 忘了初始化 dp[0]
    • 子遮罩迭代寫錯：要用 (submask - 1) & mask
    • 用某個位元前沒先檢查它是不是 1
    • 1 << n 讓 int 溢位（n ≥ 31 要用 1L << n）

總結

步驟 要寫什麼
1. 檢查規模 n <= 20 嗎？不是的話，位元遮罩 DP 就是選錯工具了。
2. 狀態 dp[mask]（組別／工人數會影響答案時，再加第二個維度）
3. 迭代順序 mask 由小到大 — mask 的每個子遮罩數值上都比它小，所以一定已經算好了
4. 轉移 不是「加一個元素」（O(2^n * n)），就是「切出一個子遮罩」（O(3^n)）
5. 答案 dp[(1 << n) - 1] — 也就是全集

真正會發生的三個 bug

  1. 遞迴式是用 < / > 來鬆弛，卻讓表格停在預設的 0 — 要先把它初始化成 ±infinity。
  2. 空的子遮罩其實是合法選擇時，卻寫成 for (sub = mask; sub > 0; sub = (sub-1) & mask) — 這樣會整個跳過它。
  3. n >= 31 時 1 << n 在 int 上溢位 — 要用 1L << n。
← 返回速查表 在 GitHub 上編輯 →