DP by sa072686

關於DP

動態規劃(Dynamic Programming, DP)是一種演算法的設計方式。
不具備演算法定義上固定的指令集和流程,也因此解題競賽經常出現。

DP的精神

要直接理解 DP 的精神與用法並不容易,
建議只先看個大概,實際看過一些例題,再回頭思索、理解它們。

將大問題轉成同性質小問題

則小問題會因性質相同,能再轉成同性質、但更小的問題。
直到問題規模夠小時,便能直接知道答案。
相當於求原問題的遞迴解。

例:有個 n 階段的階梯,你一次可跨上 1 或 2 個階段,
問有多少種不同的方式,踏上第 n 階段。

解:可由第 n-1 階段跨 1 階,或從第 n-2 階段跨 2 階到達第 n 階,
因此 f(n) = f(n-1) + f(n-2)

計算過的小問題不重覆計算

例如第 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

狀態與壓縮

在尋求合適的遞迴解時,以狀態的概念來幫助思考。

以一或多個數字為一組狀態,來表達一個情境。

例如上述的爬樓梯問題,便是用 dp[n] 表達爬到第 n 階上面,共有多少種方法。

如果某些情況在未來擁有完全相同的發展,就能壓縮成相同狀態看待。

能夠將越多種情形,壓縮到越少的狀態,執行效率就會更高。

例如上述的爬樓梯問題,實際上 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 階上」的結果,擁有相同的特性、相同的未來發展,
因此可被壓縮至同一個狀態,視為相同情形對待。

狀態的壓縮某程度可說是刻意的不完整描述所導致的結果。
由於描述的不完整,使得某些不同的走法,被忽略掉其它差異,描述成相同的情況。
像是把一隻黑貓、一隻白貓,描述成「兩隻貓」的感覺。
忽略了牠們其它任何個體差異,全歸類到「貓」來描述。

轉移

轉移便是原問題如何與子問題的解產生關聯,進而從子問題的解,求得原問題的解。

例如上述的爬樓梯問題,

dp(n)=dp(n1)+dp(n2)

即為原問題與子問題的關聯性。

也可以這樣想:假如你已經知道所有的子問題的答案,如何拿來求原問題的答案?

複雜度計算

空間複雜度視狀態數量而定,時間複雜度則為狀態數量乘上轉移複雜度。

例如上述的爬樓梯問題,需要計算的狀態量為 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
  • 很多時候無須記錄子問題是否算過,省去初始化時間、沒有忘記初始化的風險

缺點:

  • 無法判斷子問題是否必要,必須全部計算不能省略

以上面兩種爬樓梯問題為例:

dp[0] = 1;
dp[1] = 1;
for (int i=2; i<=n; i++)
{
    dp[i] = dp[i-1] + dp[i-2];
}
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

直接遞迴,若已計算過則直接回傳記錄的答案;
否則在計算後存入表中,並標記已計算過。

以上面兩種爬樓梯問題為例:

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);
}
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 組輸入

使用例:

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

題目連結

大多數問題,總之將關心的東西放到狀態中,切掉尾巴通常就會變成子問題。
方法數的位置通常固定,所以試著將狀態定為:

以 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

題目連結

小孩學寫數字,但只學了 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

題目連結

考慮第 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

題目連結

在 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

題目連結

有 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

題目連結

每個數字用加或減串起來,把最後一個數字和運算子拔掉就會變成子問題。
整除和餘數有關,同餘可視為相同。

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

題目連結

在第 (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

題目連結

n 位數字,切去第 n 位雖然可形成子問題,但同樣須注意和尾巴那組數字的串接。
同之前的要訣,將完整不再分割的數字看成一組,把尾巴那組去掉,變成子問題。
不知道切哪裡好的時候,就把所有可能位置都試一遍,挑最好的。

dp[n] = k 代表前 n 位數字切割加總的最大值
dp[n] = max(dp[n-k] + to_num(n-k+1, n))  for k = [1, 10]

經典題

經典題多半有一定困難度,但可能常見、可能泛用、可能解法巧妙等,
因各種原因導致幾乎人人都會,或至少背過解法。

最大連續和

UVa 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

題目連結
題目連結

以下用 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

題目連結

直觀想法是 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 時的內容,便可寫成:

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 的意義上將完全不同,就是錯的。

for (int i=value[n]; i<=M; i++)
{
    dp[i] += dp[i-value[n]];
}

相對二維變得簡潔好寫,但若不從原先二維的狀態與轉移開始理解,
從花費許多功夫優化過的結果,是相當難消化的。

背包

UVa 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

題目連結

題目要求找出所有子序列中,元素呈嚴格遞增者,最長長度是多少。

觀察可發現嚴格遞增的序列,拔掉最後一個元素,仍是嚴格遞增的序列。
且子序列的子序列,也會是自己的子序列。
因此拔掉最後一個元素,會變成同性質的子問題。

同時,最後一個元素的值和位置,影響這個遞增子序列,能不能添加元素變得更長。
而尾巴相同的遞增子序列中,長度最長的永遠最好。
因為後續能添加的一樣,別人怎麼變長,自己跟著做就一定比別人更好。

故結尾相同時可壓縮成同一個狀態,只需保留最佳;
拔掉結尾後即為子問題。只要子問題的結尾在自己之前,且值比自己小,自己就可以接上去。

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

題目連結

注意這題的翻譯,原文的 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

題目連結

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

題目連結

撿起同樣的松果、且最後撿起的松果相同(影響最後所在位置)時,可以當作一樣的狀態。
比如說撿的順序 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

題目連結

每次決定一組人,剩下人的集合即為子問題。剩下人的集合相同時,可以當作一樣的狀態。
每個人是否存在剩下人的集合以 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

題目連結

觀察可知,拆成一堆數字相乘時,若存在合數,則合數可再拆成更多數字相乘。
質數只能拆成不符合題目條件的 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

題目連結

篩法能得出整數 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

題目連結

當每一種物品數量不只一個時,最簡單的做法就是將它們看作重量相同、價值相同的不同東西。
不過拆下去可能會非常多個。

觀察這個過程,同樣物品 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

題目連結

除了重量需要盡量接近,人數也有限制。因此人數也是重要的、需要關心的。

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

題目連結

每次去搜所有在自己之前的元素,其實做了許多無謂功。

基於貪心,如果找到長度為 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

題目連結

看似與上一題相同,由於多維而無法使用優化過的 LIS,其實不然;
剛好二維且需要排序的情形例外,按照其中一維排序後,就只需要考慮另外一維了。

例如這題希望體型嚴格遞增,而智商嚴格遞減。
按體型不遞減排序,便已確保至少體型不會變小,可以無視掉;
只須關心智商的遞減即可。

注意排序時若體型相同,排序後我們只看智商會誤接,
因此,體型相同時,智商應按照相反順序排序,像這題要按智商遞增。
如此體型相同時,智商的順序會使得同體型無法接在一起。

UVa 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

題目連結

很顯然地,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

題目連結

和上題相似,但序列元素可重覆導致配對數暴增。

同樣掃過第一個序列,不同的是字元會重覆出現,
故須用一陣列 loc[i] 儲存所有字元 i 出現的位置。

掃過第二個序列時,同樣保證了第二維的嚴格遞增;
但同 UVa 10131
第二維相同時,第一維須以大到小的順序加入,以防止第二維相同時誤接上去。

又,序列 b 中相同字元產生的配對,由於是以大到小的順序加入,
若上一個字元為結尾,可形成長度 k+1 的遞增子序列,
則下一個字元為結尾時,可形成的遞增子序列長度,由於第二維相同、第一維更小,
能形成的遞增子序列長度必不超過 k+1。

因此,對於 b 的同個字元,在 a 中的不同配對,
尋找結尾最佳長度時,只需要從上一個的位置往前找,不須每次從頭。

配對數最差 n^2 個,但同個字元只往前掃不後退,
若 LCS 長度為 m 則複雜度實質上是 n^2 + nm。

TOJ 26

題目連結

和上題相似,可轉 LIS 加速。僅供練習。

最佳二元樹

UVa 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

題目連結

費氏數列為一相當好的例子,其轉移方程 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

題目連結

在最前面就有解過,轉移方程如下:

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]

[1dp[n2]dp[n1]][adgbehcfi]=[1dp[n1]dp[n]]

  • 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

題目連結

這題需要的是將第 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

題目連結

僅供練習

排列組合

UVa 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

題目連結

與 10338 解法相似,僅供練習。

約瑟夫問題

題目連結

有 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 的倖存者了。