位元遮罩動態規劃（bitmask DP）

有時一個子問題的自然狀態是「到目前為止我處理了這個小集合中的哪些成員？」——拜訪了哪些城市、指派了哪些工作、安排了哪些人入座。一個有 n 個元素的集合的子集，可以編碼成一個 n 位元的二進位數：若元素 i 在子集中則第 i 位為 1，否則為 0。位元遮罩動態規劃就用這些子集編號來索引動態規劃表，於是一個 0 到 2^n - 1 之間的數字便完整描述了哪些元素「已完成」。當 n 最多約 20 時，子集最多約一百萬個，這是可處理的。

從 0 到 2^n - 1 的每個整數遮罩命名一個子集，而 dp[mask]（常還有第二個索引）儲存「恰好 mask 中的元素已被處理」這個情況下的最佳答案。轉移在翻轉位元：要把元素 j 加入子集就算 mask | (1 << j)；要檢查 j 是否存在就看 (mask >> j) & 1；要遍歷存在的元素就對被設定的位元做迴圈。求值順序按 popcount（位元數）遞增，或乾脆按整數值遞增即可，因為一個遮罩的轉移通常通往多設一位元的遮罩（一個嚴格超集），而「多一個位元的遮罩」是更大的整數。典型用途是指派型問題：dp[mask] = 把前 popcount(mask) 個工作恰好指派給 mask 中那些工人的最佳成本，轉移是把下一個工作交給某個尚未使用的工人。

這個成本同時是它的殺手級特點與殺手級限制。共有 2^n 個子集，每個轉移最多檢視 n 個位元，所以典型的位元遮罩動態規劃以 O(2^n 乘以 n) 時間、O(2^n) 空間執行——是指數的，但比起嘗試所有排列的 O(n!) 是巨大的進步。這使 n 必須很小：約 20 還算舒適，25 已逼近記憶體上限，超過約 30 時 2^n 就爆炸了。最著名的實例是解旅行推銷員問題的 Held-Karp 演算法。位元遮罩動態規劃恰好是在 n 小到指數級可接受、且狀態確實是「哪個子集」時的正確工具，而非 n 很大時。