DP State Design¶
介紹¶
設計 DP 狀態有一些技巧，可以加速設計的速度並 ~~增加想像力~~ ~~通靈更成功~~。
技巧¶
BFS¶
在處理 DP 問題時，題目通常會要求一個 cost，而當我們在想 DP 時，就可以用答案的拼湊方法 + cost 的計算方法來當作樹根，並往下做 BFS。\
有些 DP 問題會有一個簡單的初始操作，於是就可以藉由初始操作 + cost 計算方法當作起點與終點，做一次雙向搜尋就很有機會~~通靈~~出 DP 狀態。
例子：USACO Circular Barn Revisited¶
題目敘述：你有一個環狀牧場，有一些牛想要去到這個牧場特定位置 (位置個數 \(3 \le N \le 100\))，你可以在農場開闢一些門 (門個數 \(1 \le K \le 7\)) 來幫助這些牛不要走太多路，若把每一隻牛要走的距離加起來，請求出這些牛最少需要走多遠才可以到他們想去的位置？
解法：
- 起點：環狀 DP 先拆成鏈狀 DP => \(O(N)\) 枚舉第一個門的位置。
- 終點：觀察到每個門都會是他接下來連續區間的首項，如果我們想開一個新門 (\(r\))，那從前一個門 (\(l\)) 進入的所有牛的 \(cost = \sum_{i=l}^{r} (i - l + 1) \times a[i]\)。
- 雙向搜尋：如果要計算這個 cost，一定需要知道最後一個門在哪，也需要知道用了幾個門才可以停止放新門，因此可以想到
dp[i][j] := 使用 i 個門且最後一個門在 j 時的答案，再加上一開始的枚舉，就會變成dp[start][i][j] := 第一個門放在 start，使用 i 個門且最後一個門在 j 時的答案，就可以套 cost 公式解題！
通靈 X¶
狀態表¶
最常見的狀態¶
| 狀態 | 功能 |
|---|---|
dp[i] := 最後選擇第 i 項的答案 |
TODO |
dp[i] := 答案為 i 時的答案 |
TODO |
dp[i] := 考慮前 i 項時的答案 |
TODO |
輔助狀態¶
這種狀態通常可被優化，但是對於思考很有幫助！
| 狀態 | 功能 |
|---|---|
dp[i] := 處理第 i 項時的答案 |
減少思考難易度 |
組合狀態¶
這種 DP 使用常見狀態與輔助狀態結合來設計狀態。
| 狀態 | 功能 |
|---|---|
dp[i][j] := 考慮前 i 項 且 目前已經選 j 項時的答案 |
對付選擇 k 項滿足條件 |
dp[i][j] := 考慮前 i 項 且 某條件為 j 時的答案 |
對付不注重排列順序的問題 |
新增必須狀態¶
這種 DP 需要觀察出一個狀態可以輔助轉移，根據不同情況有一些可被化為模型，其餘只能自行想像。
| 狀態 | 功能 |
|---|---|
dp[i] := 取餘後為 i 時的答案 |
跟因數、整除、餘數有關 |
dp[i][j] := 有 i 個 奇數 / 偶數 (j) 時的答案 |
和奇偶性有關 |
dp[i] := 是否與前一項相同 (i) 時的答案 |
TODO |
dp[i][j] := 選或不選 (j) 第 i 項時的答案 |
TODO |
特殊狀態¶
| 狀態 | 功能 |
|---|---|
dp[i] := 當樣子是 i (自定義的樣態參數) 時的答案 |
可以分段 (分樣子) 討論 |
dp[l][r] := 區間 [l, r] 的答案 |
和區間有關 |
| TODO 賽局 dp | |
dp[state(2)] := 用位元儲存第 state(2) 的第 i 低位是否被用過 |
需紀錄所有可能的選擇情況 且 \(N \le 20\) |
dp[i][j] := 抵達 (i, j) 時的答案 |
二維地圖 |
TODO