動態規劃 Lecture 1B: 遞迴關係

遞迴關係

讓我們再透過幾個例子觀察問題與子問題之間的遞迴關係：

這題看起來是一個「計算有幾種答案」的組合數學問題。與數學不同的是，我們不見得會需要把答案的公式算出來，只要掌握遞迴的要領，在時間與記憶體限制之下正確地算出我們要的結果就可以了！

遞迴重點：只考慮一步

令 $\DP(n)$ 為爬到第 $n$ 階的方法總數。我們考慮所有爬到第 $n$ 階的方法：顯然最後一步僅能跨出 $1$ 階或 $2$ 階，而最後一步跨出 $1$ 階的所有方法顯然與最後一步跨出 $2$ 階的任何方法都不同，因此我們得知爬到第 $n$ 階的方法數，等於「先爬到第 $n-1$ 階再跨一階」的方法數，加上「先爬到第 $n-2$ 階再一口氣跨 $2$ 階」的方法數。於是有

有了重要的遞迴關係式以後，我們就可以考慮初始條件（或稱邊界條件）了。當 $n=1$ 的時候，僅有一種方法可以跨到第 $1$ 階樓梯。當 $n=2$ 的時候，有 $1+1$、$2$ 兩種方法可以跨到第 $2$ 階樓梯。於是我們可以完整地寫下遞迴式：

遞迴重點：儲存狀態用的資料結構

有了遞迴關係以後，我們就要設計一種資料結構，可以輕鬆存取計算過的子問題答案。 絕大多數的情形下，提供隨機存取的「陣列」會是我們的不二首選。

以爬樓梯為例，我們可以輕易地推敲出所有需要的狀態 $\DP(x)$ 為 $x=1, 2, \ldots, n$。因此開一個長度為 $n$ 的陣列最適合這樣的問題了。

動態規劃的實作方式

當我們確定了動態規劃的遞迴關係與終止條件以後，在實作上我們有兩種大方向可以參考：他們分別是 填表實作（Table Filling，又稱為 Bottom-Up 方法）以及 遞迴實作（Recursion，又稱為 Top-Down）這兩種實作方法有著各自的優缺點以及適用性，這點我們會在未來的例題中逐一探討。

填表實作 (Bottom-Up)

若我們能夠確定某種計算的先後順序，那有時我們便不需要以遞迴函式實作狀態轉移。 這麼一來我們便不需要每一次都先檢查某個子問題算過了沒有，因此程式的效率也會變高。

以爬樓梯問題為例，只要依照 $i=1, 2, 3, \ldots, n$ 的順序計算 $\DP(i)$，我們能保證計算 $\DP(i)$ 的時候 $\DP(i-1)$ 和 $\DP(i-2)$ 都已經算好了。

int climbStairs(int n) {
    dp[1] = 1; // 設定邊界條件
    dp[2] = 2;
    for (int i = 3; i <= n; i++) // 實作狀態轉移
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    return dp[n];
}

遞迴實作 (Top-Down)

在計算順序不明確，或是所需狀態總數不好估計的時候，使用遞迴實作或許可以減少一些不必要的計算。 雖然從爬樓梯問題來說，我們並不需要使用遞迴實作，但我們還是把遞迴版本寫在這裡吧～

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (used[n]) return dp[n];
    used[n] = true;
    dp[n] = climbStairs(n-1) + climbStairs(n-2); // 實作狀態轉移
    return dp[n];
}