DP 回溯

到目前爲止，我們遇見的 DP 題型目標大約有兩種：

• 找到「最佳答案的數值」，這一類題目通常被稱作最佳化問題。
• 計算「滿足條件的個數」，這一類題目通常被稱作計數問題。

在這兩類問題中，最佳化問題應用在現實上其實有一個潛在的疑慮：即使我知道了最佳答案的數值，我可能還是不知道怎麼構出最佳的答案啊？

舉例來說，在背包問題中，就算我們得到最大價值，我們依然不會知道要拿哪些物品才可以達到這個最大價值！

因此，除了求得最大價值之外，我們還得懂得如何真正把「解答方案」構造出來，像這樣利用 DP 結果來構造出答案的手法，我們便稱之為「DP 回溯」。

在下面幾個段落，我們就來分享幾個常見的 DP 回溯手法。而為了方便起見，我們皆以背包問題做為範例，在其他 DP 題上的應用就交給讀者自行應變了。

在解決 DP 問題時，我們常常會需要做出「決策」。例如背包問題的決策就是要決定每個物品拿或不拿；而決策後所帶來的結果則通常會對應到一個子問題。

這就有一個相對直觀的做法：我們可以先求一遍最佳解，接著假設最佳解需要拿第一個物品，只要這樣做之後對應到的子問題最佳解補上第一個物品後依然可以獲得最佳解，那拿走第一個物品便不成問題；否則，第一個物品就是不能拿的。

做完這樣的決策之後，我們就可以把第一個物品直接放進背包、或是直接丟棄，這樣一來我們就只要專心構造出物品 $2\sim N$ 的最佳解，再根據剛剛第一個物品的決定結果補回去就可以了！

寫成虛擬碼的話大概會是這樣的：

/*
N: 物品數量, W: 重量上限
w[i]: 第 i 個物品的重量, v[i]: 第 i 個物品的價值
solve: 背包問題的求解函數
*/

vector<int> output;
max_value = solve(1..N, W);
for (int i = 1; i <= N; ++i) {
    if (solve(i+1..N, W - w[i]) + v[i] == max_value) {
        output.push_back(i);
        W -= w[i];
        max_value -= v[i];
    }
}
// output 裡存的就是答案的構造

不過可惜的是，因為每一個物品都要這樣「重跑一次」，這樣做的時間複雜度會直接多出一個 $N$，有沒有改善的方法呢？

觀察一下上面的虛擬碼，可以發現我們需要「重跑」的背包問題子問題總是某個 $i$ 到 $N$ 的物品們，那既然背包問題物品的順序並不是很重要，我們乾脆在一開始直接倒著跑背包問題，也就是令 $dp[i][j]$ 是「考慮第 $i$ 個以後的物品中，湊出重量至多 $j$ 的最大值」，這樣上面每一次 solve(i+1..N, W - w[i]) 的詢問，就可以轉化成一個 $\mathrm{dp}[i+1][W - w[i]]$ 的 $O(1)$ 詢問了！

也因此，我們回溯出答案的時間甚至只有 $O(N)$ 而已，整個演算法的時間瓶頸就變回原本的背包問題了。

不過聰明的讀者也許有注意到，其實我們也可以不要倒著算背包問題的答案，而是在構造解的時候倒著構造就行，也就是變成：

vector<int> output;
max_value = solve(1..N, W);
for (int i = N; i >= 1; --i) { // 這裡倒著遍歷
    if (dp[i - 1][W - w[i]] + v[i] == max_value) {
        output.push_back(i);
        W -= w[i];
        max_value -= v[i];
    }
}
// output 裡存的就是答案的構造

這樣一來 DP 也不用反著算了。而在此之上也有另一種實作方式：

vector<int> output;
int cur_n = N, int cur_w = W;
while (cur_n != 0) {
    if (dp[cur_n - 1][cur_w - w[cur_n]] + v[cur_n] == dp[cur_n][cur_w]) {
        output.push_back(cur_n);
        cur_w -= w[cur_n];
        --cur_n;
    }
    else {
        --cur_n;
    }
}

在背包問題時，這種寫法可能跟前一種的看不太出差別，但如果是狀態轉移比較亂跳的題目就會明顯有差別，因為你可能不知道 cur_n, cur_w 這個狀態往前一格到底會往前跳到哪一個狀態去，也因此在一開始不能使用 for 迴圈固定跑 $N$ 次，而是得用一個 while 迴圈做為終止條件的判斷。

接下來我們再來介紹另一種方法。

回顧背包問題的轉移式：$\mathrm{dp}[i][j] = \max(\mathrm{dp}[i - 1][j], \mathrm{dp}[i - 1][j - w[i]] + v[i])$。其實這個轉移式本身就是一種決策的選擇，因此我們可以特別開一個 table $\mathrm{tr}[i][j]$，代表 $\mathrm{dp}[i][j]$ 的答案是哪一個轉移來源給予的。而 $\mathrm{tr}[i][j]$ 是可以很輕易的在計算 DP 的過程時順手維護的。

有了這個表格之後可以幹嘛呢？假設 $\mathrm{tr}[i][j] = 1$ 代表該狀態是透過取第 $i$ 種物品轉移來的、$=0$ 代表沒有取第 $i$ 種，我們可以直接把前面的第二種寫法改成這樣：

vector<int> output;
int cur_n = N, int cur_w = W;
while (cur_n != 0) {
    if (tr[cur_n][cur_w]) {
        output.push_back(cur_n);
        cur_w -= w[cur_n];
        --cur_n;
    }
    else {
        --cur_n;
    }
}

這種做法在轉移式相對複雜的時候在實作上的優勢會大很多，因為如果轉移式非常多 case，迴圈內的每個 if 都得補上長長的判斷式，好好紀錄轉移來源就沒有這個問題了。甚至如果覺得要在迴圈內手動執行 cur_w -= w[cur_n]、--cur_n 這些式子很麻煩的話，還可以讓 tr 裡面存著「從這個狀態往前跳的話會跳到哪」，這樣一口氣在一開始 DP 時把所有東西算好，DP 回溯就可以無腦寫了。

暴力「存」解是什麼意思呢？其實真的相當暴力，就是直接把解答的樣子直接存在對應 DP 的陣列裡。以背包問題來說，就是在 $\mathrm{dp}[i][j]$ 裡直接存著前 $i$ 個物品中湊出重量 $j$ 且價值最大的那些物品，而因為可能會有至多 $N$ 種物品，所以整體的複雜度會硬生生的乘上一個 $N$。

會需要這樣做的情況不太多，非得這樣做的情況通常都是為了獲得滿足特定性質的答案（例如最小字典序）、但又無法好好維護時才會退一步這樣做，讀者可以在心中有個印象即可。

有些題目還會額外要求選手輸出「最小字典序」的解答，在這種情況下，前面紀錄轉移來源那派的做法會稍微尷尬一些，雖然也是可以透過倒著跑 DP、再從最一開始進行回溯來辦到，但總是會多出一些細節。

此時，我們最一開始提到的「由後往前做」的作法優勢就出現了！因為我們是正著取答案的關係，所以第一個物品能取的話，我們就一定會先取到，後續也會保持著這樣的好處，因此這樣「貪心」的結果也就讓我們構造出來的答案自然是最小字典序了。

不過讀者要特別注意，這裡的最小字典序是「編號」的最小字典序，如果是別的意義上的最小字典序的話，讀者就可能要小心一點，視情況可能會得搬出前面的「暴力存解」來用。

基本上不行。

回顧一下前面的做法，可以發現「儲存所有子問題的答案」幾乎都是必須的，因此一旦使用了滾動 DP，就會導致先前狀態的資訊丟失，進而使 DP 回溯失效。

所以一般來說，遇到需要輸出答案的題目，可以先當成無法使用滾動 DP 會比較恰當。在這樣的情況下若題目還卡記憶體的話，可能就得考慮換一種 DP 路線、甚至是換一種做法。

不過可別太天真的以為需要輸出答案的 DP 題目就無法省記憶體，事實上根據題目特性，還是有可能有一些神秘技巧誕生，更有一類 DP 問題存在通用的做法可以省記憶體，不過這些就都得到未來的章節才會解釋了。

我們這整篇文章都是以背包問題為例，但 DP 題可是有非常多的變化可能會出現，因此建議讀者多透過習題來掌握 DP 回溯的概念。