題目描述:給定 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]。時間複雜度: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 相同,但實作上使用佇列。