動的計画法
01 / 共通の仕組み
表が 1 マスずつ自身を埋めていき、各マスは 定数個の以前のマスから合成される。 漸化式はサブパターンごとに異なるが、仕組み — 状態、遷移、埋める順序 — は共通している。
02 / 一文で言うと
状態はアイテムの部分集合、ビットマスクで表現。 各遷移は 1 つアイテムを集合に追加する。鍵となる洞察は: アイテムが選ばれた順序は重要ではなく、どの部分集合かだけが重要 —— これでN!の探索を2^Nの状態に縮約できる。
問題N タスクを N ワーカーに割り当てる最小コスト入力cost = [7, 4, 3, 3, 1, 2, 5, 8, 6]
コスト
7T0·W0
4T0·W1
3T0·W2
3T1·W0
1T1·W1
2T1·W2
5T2·W0
8T2·W1
6T2·W2
dp[mask]
0000
∞001
∞010
∞011
∞100
∞101
∞110
∞111
dp[mask] = タスク 0..popcount(mask)−1 を mask が示すワーカーに割り当てた最小コスト。dp[0] = 0 から始め、他は ∞。ビット数昇順で 2^3 個の mask を埋める。
ステップ
0 / 32
mask
—
埋めた mask
1 / 8
dp[全]
∞
0 / 32
03 / パターンの骨格
# 割り当て問題 —— popcount 昇順に埋めるdp[0] ← 0dp[mask] ← ∞ for mask ≠ 0for mask in 0..(2^N − 1):k ← popcount(mask) # 次に割り当てるアイテムの添字for j in 0..N−1 if j not in mask:dp[mask | (1 << j)] ← min(dp[mask | (1 << j)], dp[mask] + cost[k][j])return dp[(1 << N) − 1] # 全アイテム配置済
04 / このパターンを使うべき合図
「N ≤ 20」
制約が N が小さい(通常 15–20)で、答えが全部分集合を見る必要がある ——
2^N 状態が実用的という強いヒント。「各々を割り当てる / 全部選ぶ」
「各タスクをワーカーに割り当てる」「全ノードを訪問」「全スキルをカバー」のような表現 —— 答えはどの部分集合かだけに依存し、順序には依らない。
「順列に対する min / max / 数え上げ」
素朴解が「
N! 通り試す」で、コストがアイテムごとに足し算される場合 —— ビットマスク DP が接頭辞を共有し、O(2^N · N) に縮める。「Hamiltonian / TSP」
Held-Karp 形式:
dp[mask][i] = mask のノードを訪問しi で終わる最短コスト。遷移コストが末尾アイテムに依存するとき、 余分な i 次元が必要。05 / よくある落とし穴
mask の反復順序を間違える。
dp[mask | bit] に書き込む前に dp[mask] を訪れる必要がある (前向き DP)—— mask < mask | bit なので昇順走査でよい。 ただし遷移がビットを消す方向にも進むなら popcount でソートする。popcount からアイテム添字への対応を忘れる。
典型は「k 番目に割り当てるアイテムは位置
popcount(mask) にある」。 ここで off-by-one するとエラーは出ないが、同じアイテムが二重に (またはスキップされて)割り当てられる —— 答えだけが間違う。mask を「順序付き列」と扱う。
mask はどのアイテムが集合にあるかを記録し、追加された順ではない。 答えが順序に依存する場合(例:「最後に訪れたノード」)、
i 次元を追加する必要がある —— マスクだけでは足りない。j を
mask に対して反復 vs ~mask に対して反復。よくあるタイポ:未設定ビットを枚挙すべきところ設定ビットを枚挙する(逆も)。
if (mask & (1 << j)) で所属判定、反対方向は条件を反転。06 / LeetCode で練習
中級8
01Can I Win— LC 464→02Matchsticks to Square— LC 473→03Beautiful Arrangement— LC 526→04Partition to K Equal Sum Subsets— LC 698→05Campus Bikes II— LC 1066→06Maximum Compatibility Score Sum— LC 1947→07Minimum Number of Work Sessions to Finish the Tasks— LC 1986→08Fair Distribution of Cookies— LC 2305→
難しい12
01Stickers to Spell Word— LC 691→02Shortest Path Visiting All Nodes— LC 847→03Find the Shortest Superstring— LC 943→04Number of Squareful Arrays— LC 996→05Smallest Sufficient Team— LC 1125→06Maximum Students Taking Exam— LC 1349→07Parallel Courses II— LC 1494→08Distribute Repeating Integers— LC 1655→09Minimum Incompatibility— LC 1681→10Find Minimum Time to Finish All Jobs— LC 1723→11Maximize Score After N Operations— LC 1799→12Minimum XOR Sum of Two Arrays— LC 1879→
— / どれをいつ使うか
1 次元線形
添字 i での答えが、定数個の以前の添字にしか依存しない場合に使う。
家を盗む · 階段を登る · 最大部分和
2 次元グリッド
状態が2 つの添字を持つ場合 — グリッド、または相互作用する 2 つの列。
最短経路 · LCS · 編集距離
ナップサック
各アイテムが容量制約下で選ぶ / 飛ばすの判断を生む場合に使う。
部分集合和 · コイン · 分割
区間
状態が区間
(i, j) で、答えが内側の区間から合成される場合に使う。回文 · 行列連鎖 · 風船を割る
状態機械
各添字が複数の有限状態のいずれかにあり、状態間の遷移規則が決まっている場合に使う。
株 · クールダウン · 2 状態
木 DP
問題が木上にあり、各ノードの答えが子ノードの答えに依存する場合に使う。
家強盗 III · 直径 · 最大経路和
ビットマスク
状態が部分集合(通常
N ≤ 20)で、どのアイテムを選んだかだけが重要で順序は問わない場合に使う。割り当て · TSP · 最小十分チーム