Hard
691. Stickers to Spell Word
arrayhash-tablestringdynamic-programmingbacktrackingbit-manipulationmemoizationbitmask
解題說明
Stickers to Spell Word
題目描述：給定 n 種貼紙 stickers，每種貼紙上有一些小寫英文字母（每種貼紙可以無限使用）。需要拼出目標字串 target，求最少需要幾張貼紙。如果無法拼出，回傳 -1。
解題思路：使用位元遮罩（bitmask）DP。將 target 的每個字元用一個位元表示是否已被滿足。狀態 dp[mask] 表示滿足 mask 所代表的字元集合所需的最少貼紙數。
- 初始化
dp[0] = 0（空集合不需要貼紙），其餘為 INF。 - 對每個狀態
mask（從小到大），嘗試使用每張貼紙：- 找到
mask中第一個未被滿足的字元位置，只考慮包含該字元的貼紙（剪枝）。 - 模擬使用這張貼紙後的新狀態
newMask。 - 更新
dp[newMask] = min(dp[newMask], dp[mask] + 1)。
- 找到
- 回傳
dp[(1 << len) - 1]。
C++ 解法
複雜度分析
時間複雜度：O(2^n * m * n) — n 為 target 長度（最多 15），m 為貼紙數量。每個狀態嘗試每張貼紙，每次模擬花費 O(n)。
空間複雜度：O(2^n) — DP 陣列大小為 2^n。
虛擬碼
1. Precompute character frequency for each sticker
2. Initialize dp[0..2^n-1] = INF, dp[0] = 0
3. For each mask from 0 to 2^n - 1:
a. If dp[mask] == INF, skip
b. Find first unset position in mask
c. For each sticker containing target[firstUnset]:
- Simulate applying sticker: greedily match remaining unset characters
- Compute newMask
- dp[newMask] = min(dp[newMask], dp[mask] + 1)
4. Return dp[2^n - 1] or -1 if INF其他解法
記憶化搜尋（字串 DP）：用排序後的剩餘字串作為狀態，透過雜湊表進行記憶化。每次選擇一張貼紙，從剩餘字串中移除對應字元。狀態空間更靈活但可能較大。適合 target 較短的情況。
BFS：將每個「剩餘字元狀態」視為圖中的節點，每張貼紙是一條邊，用 BFS 找最短路。本質與 bitmask DP 相同，但實作上使用佇列。
延伸思考
- 為什麼要固定先處理第一個未滿足的字元？這個剪枝的正確性如何保證？
- 如果 target 長度超過 15，bitmask DP 不再可行，有什麼替代方案？
- 如果每種貼紙只能用一次，問題會變成什麼？該如何修改？