owned this note
owned this note
Published
Linked with GitHub
# DP by sa072686
- [基礎題單](http://skyoj.tnfsh.tn.edu.tw/sky/index.php/rank/view/37)
- [綜合題單](http://skyoj.tnfsh.tn.edu.tw/sky/index.php/rank/view/38)
# 關於DP
動態規劃（Dynamic Programming, DP）是一種演算法的設計方式。
不具備演算法定義上固定的指令集和流程，也因此解題競賽經常出現。
## DP的精神
要直接理解 DP 的精神與用法並不容易，
建議只先看個大概，實際看過一些例題，再回頭思索、理解它們。
:::success
### 將大問題轉成同性質小問題
則小問題會因性質相同，能再轉成同性質、但更小的問題。
直到問題規模夠小時，便能直接知道答案。
相當於求原問題的遞迴解。
```
例：有個 n 階段的階梯，你一次可跨上 1 或 2 個階段，
問有多少種不同的方式，踏上第 n 階段。
解：可由第 n-1 階段跨 1 階，或從第 n-2 階段跨 2 階到達第 n 階，
因此 f(n) = f(n-1) + f(n-2)
```
:::
:::success
### 計算過的小問題不重覆計算
例如第 n 階乘，或者費氏數列第 n 項，不管計算多少次答案均不變，
故可將計算過的部份存下來，避免無謂的重覆計算
```
例：將費氏數列第 6 項遞迴展開
f(6)
/ \
f(5) f(4)
/ \ / \
f(4) f(3) f(3) f(2)
/ \ / \ / \
f(3) f(2) f(2) f(1) f(2) f(1)
/ \
f(2) f(1)
實際上只需要計算 f(1) ~ f(6) 共 6 種情況，卻產生了許多非必要的重覆計算。
若我們將計算結果儲存下來，則會剩下這樣：
f(6)
/ \
f(5) f(4)
/ \
f(4) f(3)
/ \
f(3) f(2)
/ \
f(2) f(1)
```
```
例二：若將費氏數列第 n 項遞迴展開，需要呼叫多少次 function 才能算完？
解：呼叫 f(n) 1 次。
f(n) 會再去呼叫 f(n-1) 以及 f(n-2)，所以再加上第 n-1 項和第 n-2 項的呼叫次數。
得出 g(n) = g(n-1) + g(n-2) + 1
我們知道費氏數列成長很接近 2^n，但 function 呼叫次數約為費氏數列本身的 2 倍左右。
不要小看那個 +1，累積起來非常可怕的。
n 1 2 3 4 5 6 7 8 9 10 11 12 13
f(n) 1 1 2 3 5 8 13 21 34 55 89 144 233
g(n) 1 1 3 5 9 15 25 41 67 109 177 287 465
```
:::
## 狀態與壓縮
在尋求合適的遞迴解時，以狀態的概念來幫助思考。
:::success
以一或多個數字為一組狀態，來表達一個情境。
:::
例如上述的爬樓梯問題，便是用 `dp[n]` 表達爬到第 n 階上面，共有多少種方法。
:::success
如果某些情況在未來擁有**完全相同的發展**，就能壓縮成相同狀態看待。
:::
能夠將越多種情形，壓縮到越少的狀態，執行效率就會更高。
例如上述的爬樓梯問題，實際上 `dp[5]` 壓縮了以下 8 種情形：
```
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 2 2
2 1 2
2 2 1
```
這些可能性最後全造成了「站在第 5 階上」的結果，擁有相同的特性、相同的未來發展，
因此可被壓縮至同一個狀態，視為相同情形對待。
:::info
狀態的壓縮某程度可說是刻意的不完整描述所導致的結果。
由於描述的不完整，使得某些不同的走法，被忽略掉其它差異，描述成相同的情況。
像是把一隻黑貓、一隻白貓，描述成「兩隻貓」的感覺。
忽略了牠們其它任何個體差異，全歸類到「貓」來描述。
:::
## 轉移
轉移便是原問題如何與子問題的解產生關聯，進而從子問題的解，求得原問題的解。
例如上述的爬樓梯問題，
$dp(n) = dp(n-1) + dp(n-2)$
即為原問題與子問題的關聯性。
:::info
也可以這樣想：假如你已經知道所有的子問題的答案，如何拿來求原問題的答案？
:::
## 複雜度計算
空間複雜度視狀態數量而定，時間複雜度則為狀態數量乘上轉移複雜度。
例如上述的爬樓梯問題，需要計算的狀態量為 n 個，空間複雜度 O(n)。
時間複雜度為狀態量 n 乘以轉移 2，共是 2n，時間複雜度 O(n)。
# 問題分類
DP 主要用來解最佳化問題，或者計算有多少種可能情形。
## 計數型
計算有多少種情形的題型。上述的爬樓梯問題即為一例。
```
計數型的轉移必須包含所有可能情形，才不致於少算。
各種情形必須完全獨立不重覆，才不致於多算。
```
例如上述的爬樓梯問題，踏上第 n 階段，最後一步肯定是跨一階，或者跨兩階其中一種。
所以包含所有情形，沒有少算。
又，從 dp[n-1] 而來的情形，最後一步一定是跨一階；
從 dp[n-2] 而來的情形，最後一步一定是跨兩階。
透過最後一步的差異，這兩種情形完全獨立沒有交集，因此沒有多算。
既沒有多算、也沒有少算，那麼數量就會剛好。
## 最佳化型
計算問題的最佳解，例如將爬樓梯問題改成：
```
有 n 個非負整數，第 i 個代表踏上第 i 個階段要付多少錢。
每次只能跨一階或兩階，問踏上第 n 階最少要付多少錢。
```
就會變成最佳化問題。
第 n 階要嘛從第 n-1 階跨 1 階上來，要嘛從第 n-2 階跨 2 階上來。
最小花費會是兩者取較佳者，加上踏上第 n 階所付的錢：
```
dp[n] = min(dp[n-1], dp[n-2]) + cost[n]
```
### 使用條件
狀態需滿足`「當子問題最佳，原問題才能得到最佳解」`的前提，才能使用 DP 解。
如同前述，踏上第 5 階的方法數其實共有 8 種。
當我們將這 8 種壓縮在同一個狀態，並且僅保留最佳解時，
這代表另外 7 種並非最佳解的可能性，全被捨棄掉了。
我們可以證明這題的解法，僅當子問題最佳，原問題才能得到最佳解。
```
如果踏上第 5 階時，最佳解是付 10 塊錢。
假設存在一組踏上第 n (n > 5) 階的最佳解，在第 5 階付了 12 塊錢。
那麼我們改採用踏上第 5 階時，只要付 10 塊錢的走法，
跟著最佳解的走法走，則第 5 階之後所付的錢會跟假設的最佳解完全相同。
第 5 階之後付的錢完全相同，但在踏上第 5 階時少付了 2 塊錢，比最佳解更佳，因此矛盾。
故不存在任何最佳解，其過程的子問題並非是最佳的。
```
以下是另一個例子，在子問題最佳時，原問題未必能得到最佳解。
```
同上述爬樓梯最小花費問題，改求踏上第 n 階時，付的錢個位數要最小。
```
則我們在第 5 階若有個位數 6 和 9 兩種可能，此時最佳花費應為 6；
但踏上第 6 階時若花 2 塊錢，則最佳花費應是 9+2 得到個位數 1，而非 6+2 的 8。
但 9 並非子問題的最佳解，而是被子問題所捨棄的可能性。
### 狀態的增維
除了把狀態完全換掉之外，對狀態追加描述、進行增維，也可能解決這種問題。
```
將狀態改為 dp[i][j] 代表踏上第 i 階時，花費個位數 j 是否可能達成。
dp[i][j] = (dp[i-1][k] || dp[i-2][k]) // k 滿足 k+cost[i] 個位數為 j
```
# 實作面
建立一個一或多維陣列 dp，用以保存已計算的子問題的解。
在計算過程中，若子問題已計算過，則直接查表得到解答，不再重覆計算。
計算過後，將計算的問題的解填入 dp 中。
## 邊界
邊界問題為 DP 最容易出 bug 的地方之一，但各種問題邊界注意事項不一，難以一一提及。
以下列幾個共通或常用的：
* 從最小問題起手，例如階乘從 0! 開始
* 從 0 開始考慮，什麼都沒有、或什麼都不取，也是一種情形
## Bottom-up
從小問題做起，慢慢往大問題推。
順序上須保證每個問題被計算時，所有需要的子問題皆已算完。
優點：
* 省去許多 function 呼叫，速度較快、絕不會 stack-overflow
* 很多時候無須記錄子問題是否算過，省去初始化時間、沒有忘記初始化的風險
缺點：
* 無法判斷子問題是否必要，必須全部計算不能省略
以上面兩種爬樓梯問題為例：
```c
dp[0] = 1;
dp[1] = 1;
for (int i=2; i<=n; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
```
```c
dp[0] = 0;
dp[1] = cost[1];
for (int i=2; i<=n; i++)
{
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
```
## Top-down
直接遞迴，若已計算過則直接回傳記錄的答案；
否則在計算後存入表中，並標記已計算過。
以上面兩種爬樓梯問題為例：
```c
int calc(int n)
{
if (used[n])
{
return dp[n];
}
used[n] = 1;
if (n < 2)
{
return dp[n] = 1;
}
return dp[n] = calc(n-1) + calc(n-2);
}
```
```c
int calc(int n)
{
if (used[n])
{
return dp[n];
}
used[n] = 1;
if (n == 0)
{
return dp[0] = 0;
}
if (n == 1)
{
return dp[1] = cost[1];
}
return dp[n] = min(calc(n-1), calc(n-2)) + cost[n];
}
```
### used && count 優化
在 Top-down 會需要記錄子問題是否計算過，這在每組輸入影響答案時必須初始化。
初始化十分耗時，又有忘記初始化的風險，以下這招可以避開這些問題：
```
used[i] = j 記錄狀態 i 最後一次被用過是在第 j 組輸入
```
使用例：
```c
int cnt; // 記錄現在第幾組輸入，每組輸入後 cnt++;
int used[N]; // 宣告在全域時預設值會全是 0，但區域變數無此特性
used[i] = cnt; // 標記狀態 i 已被用過
used[i] = 0; // 取消標記狀態 i
if (used[i] == cnt) // 用以判斷 i 是否用過；若用過則其值應為 cnt，沒用過則 != cnt
```
### 回溯解
最佳化問題有時會要你輸出其中一組最佳解，因此必須能回溯解。
最佳化問題通常是原問題在子問題中，從最佳的子問題轉移而來；
對每個狀態記錄是從哪一個子問題轉移而來，則透過狀態轉移的遞迴性質可回溯出一條路徑。
路徑上所有狀態即是其中一組最佳解。
#### 字典序最佳解
有的問題會要求若有多組最佳解，選擇字典序最小或其它優先條件。
在這種情況需注意轉移順序，因為字典序可以 greedy，只要前面的字更小，後面的字無法抗衡。
回溯是從尾巴回去，例如有兩組解 bed 以及 tea，
則回溯順序是 d -> e -> b 以及 a -> e -> t，
顯然就算結尾狀態記錄較 d 為佳的 a 也會因為最前面 b 比 t 好而整個逆轉。
故意把 DP 倒著做，回溯順序就會反轉，變成 b -> e -> d 和 t -> e -> a，
回溯出來的解就不可能被逆轉，一定是最優的那一個。
# 例題
儘管 DP 並無定形，要訣卻是共通的。
一邊練習 DP 思考問題的方式，一邊把握各種定義出狀態、轉成子問題的方式，
是掌握運用 DP 的感覺最佳的方式。
仔細看的話，下列例題雖然天差地遠，其實有相當多相似之處。
最常見手法是將最後一組拿掉，看它能有什麼操作、或子問題的什麼因素會影響它。
## UVa 369
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?369)
大多數問題，總之將關心的東西放到狀態中，切掉尾巴通常就會變成子問題。
方法數的位置通常固定，所以試著將狀態定為：
```
以 dp[n][m] = k 代表在 n 個物品中取出 m 個，共有 k 種方法
```
這 n 個物品，每一個我們都能夠選擇取，或者不取，兩種可能。
比如說 4 取 2 則有以下幾種可能：
```
1234
----
OOXX => 12
OXOX => 13
OXXO => 14
XOOX => 23
XOXO => 24
XXOO => 34
```
尾巴就是第 n 個，這東西必定要決定取或不取。
把第 n 物拿開，剩下 n-1 個東西就會變成同性質子問題。
若取第 n 物，則餘下 n-1 個中，要剛好取 m-1 個，加上第 n 個剛好；
若不取第 n 物，則餘下 n-1 個中，要剛好取 m 個才會剛好。
```
取第 n 個 不取第 n 個
dp[n][m] = dp[n-1][m-1] + dp[n-1][m]
```
所有可能中，第 n 個東西必定只有取和不取兩種情況，故沒有少算；
兩種方法中一邊必定有 n 一邊必定沒有 n 所以沒有多算。
## UVa 10198
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10198)
```
小孩學寫數字，但只學了 1, 2, 3, 4 且認為 4 的值和 1 是相同的。
他還沒有十進位概念，因此若要表達 5，他可以寫 122 這樣加起來剛好是 5。
但他也可以寫 212 或 14414 加起來也會是 5，給你 n 求小孩共有多少方式表達數字 n。
```
不管數字怎麼寫，最後一個數字必定是 1, 2, 3, 4 其中之一。
拿掉最後一個數字後，剩下的數字就會變成同性質子問題。
若結尾是 1，那麼剩餘數字加總應是 n-1。
若結尾是 2，那麼剩餘數字加總應是 n-2。
若結尾是 3，那麼剩餘數字加總應是 n-3。
若結尾是 4，那麼剩餘數字加總應是 n-1。
```
dp[n] = k 表示寫出數字 n 的方法數共有 k 種
dp[n] = dp[n-1] + dp[n-2] + dp[n-3] + dp[n-1]
```
## UVa 10401
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10401)
考慮第 i 直行，由於皇后受傷，攻擊範圍往右只有一格距離，
因此只有第 i-1 直行的皇后位置能夠影響自己可擺放位置，而這是重要的、需要分別的。
但第 i-2 或更之前的直行的皇后位置則不重要，可以壓縮在同一個狀態中。
第 i-1 直行的皇后，只要不攻擊到自己就可以了。
換言之，第 i 直行放在第 j 橫排的話，只要第 i-1 直行的皇后，
不在第 j-1, j, j+1 橫排，就不會互相攻擊。
```
dp[i][j] = k 代表有 i 個直行的棋盤上，第 i 直行的皇后放在第 j 橫排有 k 種方法
dp[i][j] = sum(dp[i-1][k]) for k != (j-1, j, j+1)
```
## UVa 10721
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10721)
在 n 條長條、剛好有 k 組相同時，第 n 條只有兩種情形，亮或者暗；
若是和第 k 組亮暗相同，則會歸在同一組；若不同則變成新的一組。
一組至多只有 m 條，所以第 k 組有幾條也是重要的。
```
dp[i][j][p][q] 代表 i 條長條，有 j 組，第 j 組有 p 條，q 代表第 j 組亮暗
dp[i][j][p][q] = dp[i-1][j][p-1][q] // 第 i 條亮暗相同，湊成一組
+ sum(dp[i-1][j-1][k][1-q]) // 亮暗不同，窮舉 j-1 組有幾條
```
十分複雜，所以改良一下，不要把條看成單位，而把組看成單位。
第 k 組只有 m 種可能，1~m 條；最左邊一定是暗，所以 k 的奇偶就是亮暗。
因此把不要的第 j 組有幾條和亮暗去掉，降維之後變成：
```
dp[i][j] = k 代表 i 條湊成 j 組有 k 種方法
dp[i][j] = sum(dp[i-a][j-1]) for a = 1~m
```
## UVa 10664
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10664)
有 n 個東西每個取或不取，因此把第 n 個拿掉就會變成子問題。
這題關心的是重量，而同樣 n 物，重量相同的情況可視為相同。
```
dp[n][m] = 0 or 1 代表前 n 物湊出重量 m 是否可能
dp[n][m] = dp[n-1][m] || dp[n-1][m-w[n]]
```
## UVa 10036
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10036)
每個數字用加或減串起來，把最後一個數字和運算子拔掉就會變成子問題。
整除和餘數有關，同餘可視為相同。
```
dp[n][m] = k 代表前 n 個數字湊出餘數 m 是否可能
dp[n][m] = dp[n-1][(m+M-num[n])%M] or dp[n-1][(m+num[n])%M]
```
## UVa 116
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?116)
在第 (i, j) 格，肯定是從第 i-1 排的第 j-1, j, j+1 這三格過來。
不管前面怎麼走，只要到了第 (i, j) 格後，往後的發展都會一樣。
也就是說，在這格不是最佳的時候，不管怎麼走，只要最佳解走一樣路線就會更好。
```
dp[n][m] = k 代表走到這一格上的最佳解是 k
dp[n][m] = min(dp[n-1][m-1], dp[n-1][m], dp[n-1][m+1]) + ary[n][m]
```
## UVa 11258
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?11258)
n 位數字，切去第 n 位雖然可形成子問題，但同樣須注意和尾巴那組數字的串接。
同之前的要訣，將完整不再分割的數字看成一組，把尾巴那組去掉，變成子問題。
不知道切哪裡好的時候，就把所有可能位置都試一遍，挑最好的。
```
dp[n] = k 代表前 n 位數字切割加總的最大值
dp[n] = max(dp[n-k] + to_num(n-k+1, n)) for k = [1, 10]
```
# 經典題
經典題多半有一定困難度，但可能常見、可能泛用、可能解法巧妙等，
因各種原因導致幾乎人人都會，或至少背過解法。
## 最大連續和
### UVa 10684
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10684)
暴力的做法是窮舉連續和的起點和終點，再把中間全部加起來。
起終點共有 n^2 對，每對花 n 的時間掃過，複雜度 n^3。
固定起點 i，掃每個終點 j 時用 [i, j-1] 的連續和加上 j 的值，可求出 [i, j] 段的和。
這樣可以降到 n^2。
考慮所有連續和必定以某個 j 為結尾，而對於特定結尾 j，要嘛和 j-1 連起來，要嘛不連。
連起來的話，則從 j-1 往前總和越大越好，也就是結尾為 j-1 的最大連續和最佳。
而不連的時候表示以 j 開頭，又 j 為結尾，故只有 j 自己。
於是發現以 j 為結尾的最大連續和，和 j-1 為結尾的最大連續和有關，又屬於同性質問題。
```
dp[n] = k 代表以 n 為結尾時，最大連續和為 k
dp[n] = max(dp[n-1], 0) + ary[n] // 0 代表不接上 j-1
```
### UVa 108 && 10755
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?108)
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10755)
以下用 108 來講解，10755雖然多了一維，依此類推即可。
暴力做法是窮舉每個子矩形的左上角和右下角，每個角是一個點對，一個點對需要 n^2 的複雜度，
兩個點對要 n^4，計算子矩形總和 n^2，總共是 n^6。
固定上邊界和下邊界後，決定左右邊界 (i, j) 時，子矩陣和可從左右邊界為 (i, j-1) 時，
再加上 j 這一直行的值而來，上下邊界 n^2，左右邊界 n^2，從上邊界加到下邊界 n，
成功降到 n^5。
若先建表 tbl[n] 代表陣列第一個元素到第 n 個元素的總和，
則 tbl[n] = tbl[n-1] + ary[n]
透過 tbl[j] - tbl[i-1] 可以快速求出 ary[i] 到 ary[j] 的總和。
```
tbl[i-1] = ary[1] + ary[2] + ... + ary[i-1]
tbl[j] = ary[1] + ary[2] + ... + ary[i-1] + ary[i] + ... + ary[j]
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
```
將一直行用一次的減法算出總和，這樣可以省去計算直行總和的複雜度 n。
到這裡降到了 n^4，已足夠解出此題。
運用同樣的技巧，我們可以在決定上下邊界後，將每一直行用一次減法算出總和，壓成一維，
就變成經典的最大連續和問題了。
## 找零錢
### UVa 674
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?674)
直觀想法是 n 元可以透過窮舉硬幣面額 1, 5, 10, 25, 50 作為尾巴，
得到 dp[n] = dp[n-1] + dp[n-5] + dp[n-10] + dp[n-25] + dp[n-50]
但這是不對的，例如 dp[6] 取一元硬幣從 dp[5] 轉移而來時，有 5+1 這種方法；
而取五元硬幣從 dp[1] 轉移而來時，有 1+5 這種方法，但這是重覆計算。
為了避免這種排列順序不同，組合卻相同的情形，我們希望讓小的先放、大的後放，
這樣保證了順序必定由小至大，不會反過來，不會出現僅排列不同的問題。
考慮前 n 種硬幣組成金額 m 的情形，可以分成使用第 n 種硬幣，以及不使用，共兩種可能。
不使用的話就只靠前 n-1 種硬幣；使用的話就必須前 n 種組成 m-value[n]，
加上第 n 種硬幣剛好金額 m。
```
dp[n][m] = k 代表以面額前 n 大的硬幣，組成總金額 m 的方法數為 k
dp[n][m] = dp[n-1][m] + dp[n][m-value[n]]
```
dp[n-1][m] 定義上必不包含第 n 種硬幣；
而 dp[n][m-value[n]] 則包含 0 至多個第 n 種硬幣，加上一個第 n 種硬幣，則至少有 1 個。
於是兩邊獨立不交集，又互相補完 0 和多個第 n 種硬幣的可能情形。
#### 滾動數組
考慮第 n 種硬幣時，從轉移來看，實際上只需要 dp[n] 和 dp[n-1] 兩條陣列。
因此，可用兩條陣列 p, q 分別代表 dp[n-1] 和 dp[n]，之後交替代表 dp[n] 和 dp[n-1]，
即為滾動數組，可將空間複雜度自 nm 降至 2n。
實際實作有幾種方式：
* 寫兩份轉移 p->q 和 q->p，視奇偶互相交替。
* 自 p 轉移到 q 之後，將 q 整個陣列複製至 p。
* 宣告 int dp[2][M]; 並用 dp[n&1] 和 dp[(n-1)&1] 分別代表 q 和 p
註：&1 運算與 %2 （除以二取餘數以判斷奇偶）等價
* 宣告兩條陣列和兩個指標 p, q 並透過交換 p, q 來輪替。
第一個方法程式碼多重覆、容易出錯、寫錯時不易修正，十分不建議。
第二個方法執行效率不佳。
第三和第四差不多，儘管除法取餘不快，但位運算 & 十分快速。
#### 只用一條陣列
考慮到方向性，m 轉移時必往較小的 m-value[n] 去，方向單一，故可只用一條陣列。
剛進到第 n 種硬幣時，陣列中全是 n-1 時的內容。
正巧轉移中也需要 n-1 時的內容，便可寫成：
```c
dp[m] += dp[m-value[n]];
```
又，考慮 m-value[n] 是取 dp[n] 的，而不是 dp[n-1] 的，
因此必須保證考慮 m 時，所有 < m 的地方都已是 dp[n]，而非 dp[n-1] 的內容。
故迴圈從 0 開始往後掃，才能保證在考慮 m 時，所有比 m 小的全都已被掃過，
已被掃過就表示內容已被從 dp[n-1] 更新到 dp[n] 了。
如果順序相反，則 DP 的意義上將完全不同，就是錯的。
```c
for (int i=value[n]; i<=M; i++)
{
dp[i] += dp[i-value[n]];
}
```
相對二維變得簡潔好寫，但若不從原先二維的狀態與轉移開始理解，
從花費許多功夫優化過的結果，是相當難消化的。
## 背包
### UVa 10130
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10130)
有 n 個物品，每個取或不取；則拿掉第 n 個物品，便是子問題。
相同重量時我們希望價值越高越好，故將相同重量不同價值壓縮起來。
進一步思考，重量較大時的最高價值，一定不比重量較小時低。
因此考慮重量 m 的時候，可將重量 m 以內的一併考慮進來，
也省去窮舉可能達成的重量的功夫。
狀態設為 n 個物品時，重量 m 以內的最大價值為 k，
第 n 件物品有兩種選擇：取，或者不取。
若取，則前 n-1 件物品重量需在 m-weight[n] 以內。
若不取，則前 n-1 件物品的重量只要在 m 以內即可。
```
dp[n][m] = k 代表前 n 件物品，總重量 <= m 的所有情況，最大價值為 k
dp[n][m] = max(dp[n-1][m], dp[n-1][m-weight[n]] + price[n])
```
同理可使用滾動數組，不再贅述。
#### 只用一條陣列
同理，但這裡 m-weight[n] 是要 dp[n-1] 的，
因此須保證在考慮 m 的時候，所有 < m 的部份都要維持仍是 dp[n-1] 的狀態。
迴圈順序必須從大到小，才能保證考慮 m 的時候，所有 < m 的地方仍未掃過，
維持 dp[n-1] 時的狀態。
細節參考找零錢的部份。
## 最長遞增子序列（LIS）
序列是一個有序的集合，順序不同視為不同。
子序列為原序列刪去 0 到 任意多個元素後，形成的新序列。
每個元素可選刪與不刪，擁有 n 個元素的序列，共有 2^n 種子序列。
自己也是自己的子序列。
### UVa 497
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?497)
題目要求找出所有子序列中，元素呈嚴格遞增者，最長長度是多少。
觀察可發現嚴格遞增的序列，拔掉最後一個元素，仍是嚴格遞增的序列。
且子序列的子序列，也會是自己的子序列。
因此拔掉最後一個元素，會變成同性質的子問題。
同時，最後一個元素的值和位置，影響這個遞增子序列，能不能添加元素變得更長。
而尾巴相同的遞增子序列中，長度最長的永遠最好。
因為後續能添加的一樣，別人怎麼變長，自己跟著做就一定比別人更好。
故結尾相同時可壓縮成同一個狀態，只需保留最佳；
拔掉結尾後即為子問題。只要子問題的結尾在自己之前，且值比自己小，自己就可以接上去。
```
dp[n] = k 代表以 n 為結尾的遞增子序列，最長長度為 k
dp[n] = max(0, dp[k]) + 1 for k < n && seq[k] < seq[n]
```
## 最長共同子序列（LCS）
對兩序列 a, b 求最長序列 s 使其滿足既是 a 的子序列，同時是 b 的子序列。
### UVa 10405
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10405)
注意這題的翻譯，原文的 subsequence 是子序列而不應是子字串 (substring)；
子字串的定義是從一字串第 i 個字元到第 j 個字元，必須是連續的。
觀察兩個序列 a, b 假設它的最長共同子序列為 s，
我們看 a 的最後一個字元 a[n] 以及 b 的最後一個字元 b[m]，
s 只有四種可能：
* s 的最後一個字元是 a[n]
* s 的最後一個字元是 b[m]
* s 的最後一個字元既不是 a[n] 也不是 b[m]
* s 的最後一個字元既是 a[n] 又是 b[m]
當 a[n] == b[m] 的時候，則一定是第四種情形最佳；
否則 a[n] 和 b[m] 至少有一個字元跟其它字元成對出現在 s 中，
若都不是，那麼 s 可以透過加入 (a[n], b[m]) 變得更佳，那就不是最佳解。
但是這種情況把 s 的最後一個字元換成 (a[n], b[m]) 也不會變糟，可能性相同。
這時 s 會是 a 的前 n-1 個字元，和 b 的前 m-1 個字元的 LCS 再接上 (a[n], b[m])，
成功找到同性質子問題。
如果不是，考慮剩下三種情形：
若是第一種，那麼把沒用上的 b[m] 拿掉後，s 不變；
若是第二種，那麼把沒用上的 a[n] 拿掉後，s 不變；
第三種拿掉哪邊都不變，可以不考慮。
由於我們不會知道 s 長什麼樣，不如說正是不知道 s 長什麼樣，才需要求解；
所以無法判斷該拿掉 b[m] 還是 a[n]，但可以知道只有這兩種可能性，
那就都試試看。
```
dp[n][m] = k 代表 a 的前 n 個字元和 b 的前 m 個字元，其 LCS 長度為 k
dp[n][m] = dp[n-1][m-1] + 1 if a[n] == b[m]
or max(dp[n-1][m], dp[n][m-1]) else
```
## 最佳矩陣連乘順序
### UVa 348
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?348)
n 個矩陣連乘的結果，最後必定會變成一個矩陣。
而最後這一個矩陣，會是過程中剩下的最後兩個矩陣相乘而來。
每個乘號會將兩個矩陣變成一個。
假設最後一個乘號是第 k 個乘號，
則以此乘號將運算式分成兩邊，各自乘成一個矩陣後，
再透過第 k 個乘號乘起來，就是最後結果。
被乘號分開的兩邊，各自互不相干，各自是一個運算式，
或者一開始就只有一個矩陣（雖然這也算一個運算式）。
因此找到了子問題，但是不能判斷 k 是哪一個，
那就每個都試試看。
```
dp[n][m] = r 代表從第 i 個矩陣連乘至第 j 個矩陣，最少乘法次數為 r
dp[n][m] = min(dp[n][k] + dp[k+1][m] + mul(n, k, m)) for k = [n, m-1]
// mul(n, k, m) 為矩陣 [n, k] 和矩陣 [k+1, m] 相乘所需次數
```
# 進階技巧
## 2^n
當有 n 個東西，互相順序可對調，求最佳順序時可用。
將用過和沒用過編碼成 2^n 則可將用過的集合相同時的狀態壓縮起來。
### UVa 10944
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10944)
撿起同樣的松果、且最後撿起的松果相同（影響最後所在位置）時，可以當作一樣的狀態。
比如說撿的順序 1→3→6→2 和 3→1→6→2 可以看作一樣，因為撿起的都是 1, 2, 3, 6
且最後所在位置都是松果 2 所在位置上。
後續可撿、需要撿的松果相同，出發位置也相同。
```
dp[n][m] = k 代表已撿松果集合 n (以二進制表示) 所在位置 m 最佳步數為 k
dp[n][m] = min(dp[n-(1<<m)][q] + dis[q][m]) for ((1<<q) & n) != 0, q != m
// dis[q][m] 為松果 q 走到松果 m 的最小距離
```
### UVa 10911
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10911)
每次決定一組人，剩下人的集合即為子問題。剩下人的集合相同時，可以當作一樣的狀態。
每個人是否存在剩下人的集合以 0 和 1 表示，可編碼成 2^n 種狀態。
決定一組人時雖有 n^2 種配對，考慮到剩下人的集合中，最後一人遲早要被組進去，
故可直接將最後一人列入組隊，只另外幫他找一個隊友。
這樣能將 n^2 種配對降至 n 種。
例如，同樣剩下 2, 3, 5, 7 四人時，先取 2, 5 再取 3, 7
和先取 3, 7 再取 2, 5 是完全相同的意思；
與其窮舉任兩人出來配對，
不如固定把 2 抓出來，在 3, 5, 7 中找一個人當他的隊友。
反正 2 最後一定要跟某個誰組隊，放後面也沒有好處。
```
dp[n] = k 代表剩下人的集合 n (以二進制表示) 最佳距離和為 k
dp[n] = max(dp[n-(1<<p)-(1<<q)] + cost(p, q)) for p 滿足 (n & (1<<p)), p != q
// q 為滿足 (n & (1<<q)) 的最小整數；cost(p, q) 為 p, q 組隊花費
```
## 篩法
在質數篩法中，通常用 bool tbl[N] 來儲存每個數是否有「被其它質數篩掉」。
既然所有合數都是被「其他質數」篩掉，何不記下每個合數被誰篩掉？
改用 int tbl[N] 存「每個數被哪個質數篩掉」，
這樣篩法做完後，每個合數都會知道自己的其中一個質因數。
### UVa 884
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?884)
觀察可知，拆成一堆數字相乘時，若存在合數，則合數可再拆成更多數字相乘。
質數只能拆成不符合題目條件的 1 和無法讓狀況更佳的自己。
因此將 n! 質因數分解後，將每個質因數的次數相加，即為所求。
利用 n! = (n-1)! * n 的遞迴性質，馬上就找到子問題，
只剩下將 n 給質因數分解。
利用篩法得知的任意質因數 k，可得出子問題 n/k；
n 質因數分解後的次數和，為 n/k 的次數和 + 1。
為了簡化轉移式的表達，這裡假設所有質數都會篩去自己，
即對於任意質數 p 滿足 tbl[p] = p。
```
dp2[m] = s 表示整數 m 質因數分解後的次數和為 s
dp2[m] = dp2[m/tbl[m]] + 1 // tbl[m] 為篩法過程中，篩去 m 的任意質數之一
dp[n] = r 表示 n! 質因數分解後的次數和為 r
dp[n] = dp[n-1] + dp2[n]
```
### UVa 10699
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10699)
篩法能得出整數 n 的任一質因數 k，但無法知道 k 的次數，
無法知道 n/k 是不是也包含質因數 k。
那就用 log n 的時間，把所有 k 除乾淨，得出 m 為 n 的因數，且 m%k != 0。
```
for (m=n; m%k==0; m/=k);
```
則 n 一定比 m 多一個 m 並沒有的質因數 k，
並且除了 k 以外，m 擁有的質因數數量和 n 相等。
```
dp[n] = k 代表整數 n 相異質因數的個數為 k
dp[n] = dp[m] + 1 // m 為 n 除以 k 直到不整除為止的結果
```
## 更多背包問題
### UVa 711
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?711)
當每一種物品數量不只一個時，最簡單的做法就是將它們看作重量相同、價值相同的不同東西。
不過拆下去可能會非常多個。
觀察這個過程，同樣物品 n 放第一次進去時，每個狀態不取是 0 個 n，取就有 1 個 n；
放第二次時，每個狀態本來有 0~1 個 n，取的話就變成 1~2 個 n，
加上不取的 0~1 個，範圍會變成 0~2 個 n。
依此類推，放第三次會變成 0~3 個 n，第四次變成 0~4 個n，…
假如我們持有 k 個 n，何不一次放很多個 n 讓範圍快速成長到覆蓋 0~k 呢？
運用二進制的概念，如果我們持有 13 個 n，
將它們分開包裝成 2^0 個、2^1 個、2^2 個、以及剩下不足 2^3 的 6 個，共四組。
一開始共有 0 個 n；
第一組放進去時，覆蓋了 0~1 個 n；
第二組放進去時，不取覆蓋了 0~1，取覆蓋了 2~3，全部是 0~3；
第三組放進去時，不取覆蓋了 0~3，取覆蓋了 4~7，全部是 0~7；
第四組放進去時，不取覆蓋了 0~7，取覆蓋了 6~13，全部是 0~13。
結果和一個一個丟進去，同樣是覆蓋了 0~13 個 n 每一種可能，
但透過打包成 2^i 個一組，只要丟 log k 次，不需要丟 k 次。
以 k = 13 為例，只要丟 4 次，全拆一個一個丟需要 13 次。
### UVa 10032
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10032)
除了重量需要盡量接近，人數也有限制。因此人數也是重要的、需要關心的。
```
dp[n][m][o] = 0/1 代表前 n 個人中，以 o 個人湊成重量 m 是否可能
dp[n][m][o] = dp[n-1][m][o] || dp[n-1][m-w[n]][o-1]
```
觀察發現雖然最多 100 人，但最多只要求 n/2 也就是 50 人，
超過 n/2 時另一組一定 < n/2 人，所以不會掉最佳解。
dp[n][m] 就變成一個元素個數 <= 50 的 0/1 陣列，
且操作是從 dp[n-1][m] 轉移過來，或從 dp[n-1][m-w[n]] 平移 1 而來。
由於 50 < 64 故可以一 long long int 用二進制表達，
則整個會變成：
```
long long dp[N][M];
dp[n][m] = k 代表以前 n 人湊成重量 m 是否可能：若 k 二進制第 i 位為 1，則 i 個人可能
dp[n][m] = dp[n-1][m] | (dp[n-1][m-w[n]] << 1)
```
須注意 `(1 << i)` 由於 1 型別為整數常數預設的 int 因此會溢出，
需追加後綴 LL 轉型成 long long 型別常數：
```
(1LL << i)
```
小寫 `ll` 效果相同，但視認上易與 `11` 混淆，建議一律以大寫 `LL` 作為後綴。
## LIS 與 LCS
### UVa 481
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?481)
每次去搜所有在自己之前的元素，其實做了許多無謂功。
基於貪心，如果找到長度為 k 的遞增子序列，自己能接在後面，
則無需再考慮任何長度 k 以下的遞增子序列，它們一定不會更好。
考慮第 n 個元素作為結尾時，子問題的遞增子序列，最長也只到 n-1。
我們可以將長度 k 的遞增子序列，其尾巴掛在長度 k 的地方，
則只要從當前最長長度往下搜，找到第一個自己能接上的尾巴，就是最佳選擇。
考慮同樣長度 k 的遞增子序列，基於貪心，結尾更小一定不會更糟，
對任何長度 k 只需保留最小可能結尾便足夠。
用一條陣列 tail[k] = s 存長度 k 的遞增子序列中，最小結尾為 s；
則對於每一個尾巴 j，找到一個最大的 k 使得 tail[k] < j，
可知尾巴 j 最長能接在長度 k 之後，組成長度 k+1 的遞增子序列。
同時，tail[k+1] 要不是不存在，就是滿足 tail[k+1] >= j，
否則 k 就不是最大的 k 能使得 tail[k] < j，k+1 才是。
因此可將 tail[k+1] 更新成 j，因為 j 一定不會比較差。
此方法在 LIS 長度為 m 時，擁有 nm 的複雜度，儘管看起來和 n^2 沒什麼區別；
如果任一結尾 j 不是在當下最長長度 k 就接得上的話，最長長度 k 保持不變；
接得上的話，比 k 小的部份全部無須考慮，面對隨機測資時非常強。
沒特別構造測資的話，很難搞爛這個方法。
#### 進一步優化
每次更新 tail 時，從上可知 tail[k] < j <= tail[k+1]，
故 tail[k] < tail[k+1] 永遠成立，對於任意 k 都成立，
這意味著 tail 本身會呈嚴格遞增。
因此，可以對其二分搜尋，將複雜度降為 n log m。
### UVa 10131
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10131)
看似與上一題相同，由於多維而無法使用優化過的 LIS，其實不然；
剛好二維且需要排序的情形例外，按照其中一維排序後，就只需要考慮另外一維了。
例如這題希望體型嚴格遞增，而智商嚴格遞減。
按體型不遞減排序，便已確保至少體型不會變小，可以無視掉；
只須關心智商的遞減即可。
注意排序時若體型相同，排序後我們只看智商會誤接，
因此，體型相同時，智商應按照相反順序排序，像這題要按智商遞增。
如此體型相同時，智商的順序會使得同體型無法接在一起。
### UVa 103
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?103)
這是另一種 LIS 的變形，給你 n 個東西，順序任意，問最長能串多長。
順序隨意看起來很難，但只要決定好順序，就和一般 LIS 問題沒有兩樣。
對這 n 件東西排序，讓排序對於任意兩物 i, j，必定滿足以下條件：
```
如果可接成 i -> j，則 i 排在 j 前；
如果可接成 j -> i，則 j 排在 i 前；
若都不可能則隨意。
```
以這題而言，先對每一物的每一維各自排序，再對每一物做字典序排序即可。
值得注意的是，這題由於尾巴有多維，可是我們無法判斷 (2, 5) 以及 (3, 4)，
這兩個尾巴哪一個才是最好的。
不論哪一個，相較其它尾巴，都無法滿足一定不會變得更差的前提。
因此，不能只保留最佳可能、並壓縮在同一個狀態內。
沒有辦法判斷最佳。
這有兩種處理方式，一是用最基本的 n^2 做法處理。
一是將所有長度 k 可能尾巴全數保留。
但基本上這樣做已失去該優化方式的優勢，卻會讓程式碼變得十分複雜。
n^2 做法看似派不上用場，但若只會優化過的方法，便無法應付這類型的題目。
### UVa 10635
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10635)
很顯然地，LCS 那 n^2 的複雜度並不夠快。
從定義可知，序列 a, b 的共同子序列 s 中，
任何一個元素，都必定同時存在於 a 和 b 中，
因此 s 每個元素可寫作 (i, j) 代表該元素取自 a[i] 與 b[j]。
s 從定義上任意兩個元素 (i, j) 與 (p, q)，
若 (i, j) 在前，則滿足 i<p && j<q。
因此，LCS 問題可透過找出所有配對 (i, j) 使得 a[i] == b[j]，
對所有配對做順序可換的 LIS 即可得出 LCS 長度。
尋找配對時，可先掃過序列 a 記錄每個數出現位置，
再來掃序列 b，則此順序保證了第二維的嚴格遞增，故無須排序；
故轉成對第一維，也就是在 a 中的出現位置的一維 LIS，
而在 a 中的位置可以常數時間複雜度查表得出。
這題只有 n 個配對，
轉 LIS 可做到 n log n 的複雜度。
### UVa 10949
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10949)
和上題相似，但序列元素可重覆導致配對數暴增。
同樣掃過第一個序列，不同的是字元會重覆出現，
故須用一陣列 loc[i] 儲存所有字元 i 出現的位置。
掃過第二個序列時，同樣保證了第二維的嚴格遞增；
但同 [UVa 10131](https://hackmd.io/oScxoezYSJyu-DYLFzyuAw?both#UVa-10131)，
第二維相同時，第一維須以大到小的順序加入，以防止第二維相同時誤接上去。
又，序列 b 中相同字元產生的配對，由於是以大到小的順序加入，
若上一個字元為結尾，可形成長度 k+1 的遞增子序列，
則下一個字元為結尾時，可形成的遞增子序列長度，由於第二維相同、第一維更小，
能形成的遞增子序列長度必不超過 k+1。
因此，對於 b 的同個字元，在 a 中的不同配對，
尋找結尾最佳長度時，只需要從上一個的位置往前找，不須每次從頭。
配對數最差 n^2 個，但同個字元只往前掃不後退，
若 LCS 長度為 m 則複雜度實質上是 n^2 + nm。
### TOJ 26
[題目連結](http://toj.tfcis.org/oj/pro/26/)
和上題相似，可轉 LIS 加速。僅供練習。
## 最佳二元樹
### UVa 10304
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10304)
二元搜尋樹必有一個 root，
決定任一 root k 之後，則 k 的左右兩邊各被隔絕為一棵子樹，
且子樹也是二元搜尋樹。因此成功找到子問題。
不知道哪個為 root 為佳，則都試試。
```
dp[n][m] = k 代表以第 n 到第 m 個數組成一二元搜尋樹，最佳答案為 k
dp[n][m] = max(dp[n][k-1]+dp[k+1][m]+calc(n, k, m)) for k = [n, m]
// calc(n, k, m) 為連續段 [n, m] 以 k 為 root 時的額外開銷
```
#### 四邊形不等式優化
觀察二元搜尋樹 [n, m] 已知其最佳 root 為 k，
若在 m 右邊插入新元素，則左子樹 [n, k-1] 不影響，
右子樹 [k+1, m+1] 多一個元素肯定變糟。
在右子樹變糟的情況下，若 k 左移讓左子樹更小，
則右子樹只會再更糟，一定不會比較好；
若會，則 k 應不是 [n, m] 的最佳 root。
故在右插入新元素時，k 應該不變或右移，左移一定只會更糟。
同理在最左邊插入新元素，則左子樹變糟，k 不該右移。
如此若以 root[n][m] 記錄 [n, m] 的最佳 root 時，
則應滿足 `root[n][m-1] <= root[n][m] <= root[n-1][m]`，
因為 [n, m] 相當於對 [n-1, m] 最左插新元素，故 k 不該右移；
同時 [n, m] 相當於對 [n, m-1] 最右插新元素，故 k 不該左移。
對於 n 個數字，左邊界最多有 n 種，
每種左邊界其最佳 root k 隨著右邊界增長，k 只會不變或跟著增長，
相當於線性掃過，因此複雜度從原本的 n^3 加入此優化後降為 n^2。
## 轉移矩陣與快速冪
對於滿足是計數型、沒有 if 且轉移方程單純是某幾項乘特定係數的型，
可將初始項寫作矩陣、找出轉移矩陣後，轉成每乘一次轉移矩陣，就得出下一項的形式。
如此對初始矩陣 M、轉移矩陣 T 則第 n 項可在 M * T^n 找到，
又基於矩陣的交換律，T^n 可透過快速冪在 log n 次乘法內算出，
可得出時間複雜度為 轉移矩陣大小^3 * log n 的方法。
### UVa 10689
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10689)
費氏數列為一相當好的例子，其轉移方程 `f(n) = 1*f(n-1) + 1*f(n-2)`
需要兩項才能推得下一項，因此初始項需要兩項：
* f(0) = 0
* f(1) = 1
則初始矩陣為 `[0, 1]`
顯然地乘上轉移矩陣後，必須維持原大小，以乘上下一次的轉移矩陣。
故 1\*n 的初始矩陣，轉移矩陣大小為 n\*n。
將初始項和轉移後的目標寫上去，可得以下式子：
```
[f(0) f(1)] x [a c] = [f(1) f(2)]
[b d]
```
從矩陣乘法得：
* `f(1) = a*f(0) + b*f(1)`
* `f(2) = c*f(0) + d*f(1)`
可知轉移矩陣每一直行，恰為轉移後該項對轉移前每一項的係數。
從第一式推得 `a=0, b=1`
從第二式推得 `c=1, d=1`
故轉移矩陣為
```
[0, 1]
[1, 1]
```
本題會給 a, b 作為初始項 f(0) 和 f(1)，但轉移矩陣共通。
#### 快速幂的實作
快速幂常見有兩種實作方法，
第一種方法是對奇次方拆成 1 次方和 n-1 次方；
對偶數先算出 n/2 次方後自乘。
```
a^n = a^(n-1) * a if n&1
a^(n/2) * a^(n/2) else
```
好處是好學好懂好理解，壞處是最差變成 2 log n，不過這影響不大。
最大問題是過程出現的次方數變化大，難以建表。
第二種方法是對次方拆成二進制，例如 23 次方可拆成二進制 10111，
即：
```
a^23 = 1*a^16 + 0*a^8 + 1*a^4 + 1*a^2 + 1*a^1
```
壞處是相對難懂，好處是轉移矩陣共通時，由於次數共通，
轉移矩陣的 2^i 次方的結果可以不需要重新計算，能夠建表。
如果 23 用第一種方法，會得出過程 23、22、11、10、5、4、2、1 次方，
而第二種方法會得出 16、8、4、2、1 次方。
這題儘管初始項 [a, b] 隨輸入變化，由於轉移方程相同，
使用方法二則可以把過程中的轉移矩陣存下，每次無須重新計算過程中的轉移矩陣 2^i 次方。
### UVa 10518
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10518)
在最前面就有解過，轉移方程如下：
```
dp[n] = dp[n-1] + dp[n-2] + 1
```
由於推至下一項需要三項，故初始矩陣為 1\*3 大小，
而轉移矩陣則需 3\*3 大小。
```
[a d g]
[1 dp[n-2] dp[n-1]] * [b e h] = [1 dp[n-1] dp[n]]
[c f i]
```
$\left[ \begin{array} {ccc} 1 & dp[n-2] & dp[n-1] \\ \end{array} \right] * \left[ \begin{array} {ccc} a & d & g \\ b & e & h \\ c & f & i \\ \end{array} \right] =
\left[ \begin{array} {ccc} 1 & dp[n-1] & dp[n] \\ \end{array} \right]$
* `1 = a*1 + b*dp[n-2] + c*dp[n-1]`
* `dp[n-1] = d*1 + e*dp[n-2] + f*dp[n-1]`
* `dp[n] = g*1 + h*dp[n-2] + i*dp[n-1]`
推得 a=1, b=0, c=0;
d=0, e=0, f=1;
g=1, h=1, i=1;
### UVa 11486
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?11486)
這題需要的是將第 n-1 直排的 7 格，每格以 0 或 1 代表士兵有無，
轉移到第 n 直排的 7 格，每格以 0 或 1 代表士兵有無。
因此對所有可能狀態進行編碼，變成二進制 0 ~ 2^7-1，
並求出這些狀態之間彼此是否可能互相轉移。
若狀態 a 在每隻士兵各走一步後，能夠變成狀態 b 則表示狀態 a 可轉移至狀態 b。
最後得一矩陣，其 (i, j) 格代表狀態 i 是否可轉移至狀態 j，
以此為轉移矩陣，即可將 n-1 直排轉移至 n 直排。
### TOJ 416
[題目連結](http://toj.tfcis.org/oj/pro/416/)
僅供練習
## 排列組合
### UVa 10338
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?10338)
考慮 ACCDD 這個例子，如果把尾巴 D 一個一個放進去會很難計算，
將所有相同字元 D 一次拔除，則轉為子問題 ACC。
對 ACC 的所有排列方式，將兩個 D 插入，
等同於在 3 個相同物 (ACC) 中，插入 2 個相同物 (DD)，為 H(3, 2) = C(5, 3)。
```
dp[n] = k 代表前 n 種字元全放進去的排列數為 k
dp[n] = dp[n-1] * H(p, q) // p 為前 n-1 種字元總數，q 為第 n 種字元數量
```
### ACM-ICPC Live Archive 4656
[題目連結](https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=351&page=show_problem&problem=2657)
與 10338 解法相似，僅供練習。
## 約瑟夫問題
[題目連結](http://domen111.github.io/UVa-Easy-Viewer/?11351)
有 n 個人圍成一個圈圈，每數 k 個人就把那人殺掉。
在殺掉第 k 個人之後，會剩下 n-1 個人，
於是得到只有 n-1 個人的子問題。
假設這 n-1 個人，最後的倖存者是第 p 個人；
原本 n 個人的時候，我們會殺掉第 k 個人，
這時剩下的 n-1 個人，是從第 k+1 個人開始數的，
因此 n-1 個人的倖存者 p 其實是從原本 n 個人中的 k+1 數起，
故 n 個人時的倖存者為第 k+1+p 個人。
實作上由於從 0 數起的話，實際死掉的是 k-1 這個人，
```
故以 dp[n] = m 代表 n 個人時倖存者編號為 m (m 的範圍 [0, n-1])
dp[n] = (k + dp[n-1]) % n
```
假設 k=3 的情況，
n=3 時倖存者為 1：
```
編號: 012
存亡: XOX
```
0 和 2 都被殺死（以 X 表示），剩下 1 還活著（以 O 表示）。
這時考慮 n=4 的情況：
```
編號: 0123
存亡: OOOO
```
我們還不知道倖存者是誰，但第一個被殺死的會是第 k 個人，
編號是 k-1。
```
編號: 0123
存亡: OOXO
```
殺掉後得到子問題：n=3, k=3
已知的倖存者是 1，但那是從第一個人開始數的情況。
在 n=4 殺掉 2 之後，剩下的三個人會是 301
```
編號: 0123
存亡: OOXO
↓
編號: 0123
存亡: O
存亡: OO
↓
編號: 0123 (n=4視角)
編號: 12X0 (n=3視角)
存亡: O
存亡: OO
↓
編號: 0123 (n=4視角)
編號: 12X0 (n=3視角，編號 1 生存)
存亡: X
存亡: OX
```
n=3 的子問題是從第一個人（編號 0）開始數下個被殺的人，
而 n=4 轉移到 n=3 子問題時，是從被殺掉的人的下一個（編號 k）開始數下個被殺的人。
故將 n=3 子問題得到的倖存編號，重新對照一下在 n=4 時的編號，
就知道 n=4 的倖存者了。
Google Drive
Gist
Clipboard
Sign in with Wallet
