C++初探動(dòng)態(tài)規(guī)劃

「動(dòng)態(tài)規(guī)劃 dynamic programming」是一個(gè)重要的算法范式，它將一個(gè)問題分解為一系列更小的子問題，并通過存儲(chǔ)子問題的解來避免重復(fù)計(jì)算，從而大幅提升時(shí)間效率。

在本節(jié)中，我們從一個(gè)經(jīng)典例題入手，先給出它的暴力回溯解法，觀察其中包含的重疊子問題，再逐步導(dǎo)出更高效的動(dòng)態(tài)規(guī)劃解法。

如圖 14-1 所示，對(duì)于一個(gè) $3$ 階樓梯，共有 $3$ 種方案可以爬到樓頂。

圖 14-1   爬到第 3 階的方案數(shù)量

本題的目標(biāo)是求解方案數(shù)量，我們可以考慮通過回溯來窮舉所有可能性。具體來說，將爬樓梯想象為一個(gè)多輪選擇的過程：從地面出發(fā)，每輪選擇上 $1$ 階或 $2$ 階，每當(dāng)?shù)竭_(dá)樓梯頂部時(shí)就將方案數(shù)量加 $1$ ，當(dāng)越過樓梯頂部時(shí)就將其剪枝。

climbing_stairs_backtrack.cpp

/* 回溯 */
void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
    // 當(dāng)爬到第 n 階時(shí)，方案數(shù)量加 1
    if (state == n)
        res[0]++;
    // 遍歷所有選擇
    for (auto &choice : choices) {
        // 剪枝：不允許越過第 n 階
        if (state + choice > n)
            break;
        // 嘗試：做出選擇，更新狀態(tài)
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

/* 爬樓梯：回溯 */
int climbingStairsBacktrack(int n) {
    vector<int> choices = {1, 2}; // 可選擇向上爬 1 或 2 階
    int state = 0;                // 從第 0 階開始爬
    vector<int> res = {0};        // 使用 res[0] 記錄方案數(shù)量
    backtrack(choices, state, n, res);
    return res[0];
}

方法一：暴力搜索

回溯算法通常并不顯式地對(duì)問題進(jìn)行拆解，而是將問題看作一系列決策步驟，通過試探和剪枝，搜索所有可能的解。

我們可以嘗試從問題分解的角度分析這道題。設(shè)爬到第 $i$ 階共有 $dp[i]$ 種方案，那么 $dp[i]$ 就是原問題，其子問題包括:

由于每輪只能上 $1$ 階或 $2$ 階，因此當(dāng)我們站在第 $i$ 階樓梯上時(shí)，上一輪只可能站在第 $i?1$ 階或第 $i?2$ 階上。換句話說，我們只能從第 $i?1$ 階或第 $i?2$ 階前往第 $i$ 階。

由此便可得出一個(gè)重要推論：爬到第 $i?1$ 階的方案數(shù)加上爬到第 $i?2$ 階的方案數(shù)就等于爬到第 $i$ 階的方案數(shù)。公式如下：

這意味著在爬樓梯問題中，各個(gè)子問題之間存在遞推關(guān)系，原問題的解可以由子問題的解構(gòu)建得來。圖 14-2 展示了該遞推關(guān)系。

圖 14-2   方案數(shù)量遞推關(guān)系

我們可以根據(jù)遞推公式得到暴力搜索解法。以 $dp[n]$ 為起始點(diǎn)，遞歸地將一個(gè)較大問題拆解為兩個(gè)較小問題的和，直至到達(dá)最小子問題 $dp[1]$ 和 $dp[2]$ 時(shí)返回。其中，最小子問題的解是已知的，即 $dp[1]=1$、$dp[2]=2$ ，表示爬到第 $1$、$2$ 階分別有 $1$、$2$ 種方案。

觀察以下代碼，它和標(biāo)準(zhǔn)回溯代碼都屬于深度優(yōu)先搜索，但更加簡(jiǎn)潔。

climbing_stairs_dfs.cpp

/* 搜索 */
int dfs(int i) {
    // 已知 dp[1] 和 dp[2] ，返回之
    if (i == 1 || i == 2)
        return i;
    // dp[i] = dp[i-1] + dp[i-2]
    int count = dfs(i - 1) + dfs(i - 2);
    return count;
}

/* 爬樓梯：搜索 */
int climbingStairsDFS(int n) {
    return dfs(n);
}

圖 14-3 展示了暴力搜索形成的遞歸樹。對(duì)于問題 $dp[n]$ ，其遞歸樹的深度為 $n$ ，時(shí)間復(fù)雜度為 $O(2^n)$ 。指數(shù)階屬于爆炸式增長(zhǎng)，如果我們輸入一個(gè)比較大的 $n$ ，則會(huì)陷入漫長(zhǎng)的等待之中。

圖 14-3   爬樓梯對(duì)應(yīng)遞歸樹

觀察圖 14-3 ，指數(shù)階的時(shí)間復(fù)雜度是由于“重疊子問題”導(dǎo)致的。例如 $dp[9]$ 被分解為 $dp[8]$ 和 $dp[7]$ ，$dp[8]$ 被分解為 $dp[7]$ 和 $dp[6]$ ，兩者都包含子問題 $dp[7]$ 。

以此類推，子問題中包含更小的重疊子問題，子子孫孫無窮盡也。絕大部分計(jì)算資源都浪費(fèi)在這些重疊的問題上。

方法二：記憶化搜索

為了提升算法效率，我們希望所有的重疊子問題都只被計(jì)算一次。為此，我們聲明一個(gè)數(shù)組 mem 來記錄每個(gè)子問題的解，并在搜索過程中將重疊子問題剪枝。

1. 當(dāng)首次計(jì)算 $dp[i]$ 時(shí)，我們將其記錄至 mem[i] ，以便之后使用。
2. 當(dāng)再次需要計(jì)算 $dp[i]$ 時(shí)，我們便可直接從 mem[i] 中獲取結(jié)果，從而避免重復(fù)計(jì)算該子問題。

   climbing_stairs_dfs_mem.cpp
   
   /* 記憶化搜索 */
   int dfs(int i, vector<int> &mem) {
       // 已知 dp[1] 和 dp[2] ，返回之
       if (i == 1 || i == 2)
           return i;
       // 若存在記錄 dp[i] ，則直接返回之
       if (mem[i] != -1)
           return mem[i];
       // dp[i] = dp[i-1] + dp[i-2]
       int count = dfs(i - 1, mem) + dfs(i - 2, mem);
       // 記錄 dp[i]
       mem[i] = count;
       return count;
   }
   
   /* 爬樓梯：記憶化搜索 */
   int climbingStairsDFSMem(int n) {
       // mem[i] 記錄爬到第 i 階的方案總數(shù)，-1 代表無記錄
       vector<int> mem(n + 1, -1);
       return dfs(n, mem);
   }

觀察圖 14-4 ，經(jīng)過記憶化處理后，所有重疊子問題都只需被計(jì)算一次，時(shí)間復(fù)雜度被優(yōu)化至 $O(n)$ ，這是一個(gè)巨大的飛躍。

圖 14-4   記憶化搜索對(duì)應(yīng)遞歸樹

方法三：動(dòng)態(tài)規(guī)劃

記憶化搜索是一種“從頂至底”的方法：我們從原問題（根節(jié)點(diǎn)）開始，遞歸地將較大子問題分解為較小子問題，直至解已知的最小子問題（葉節(jié)點(diǎn)）。之后，通過回溯將子問題的解逐層收集，構(gòu)建出原問題的解。

與之相反，動(dòng)態(tài)規(guī)劃是一種“從底至頂”的方法：從最小子問題的解開始，迭代地構(gòu)建更大子問題的解，直至得到原問題的解。

由于動(dòng)態(tài)規(guī)劃不包含回溯過程，因此只需使用循環(huán)迭代實(shí)現(xiàn)，無須使用遞歸。在以下代碼中，我們初始化一個(gè)數(shù)組 dp 來存儲(chǔ)子問題的解，它起到了記憶化搜索中數(shù)組 mem 相同的記錄作用。

圖 14-5 模擬了以上代碼的執(zhí)行過程。

圖 14-5   爬樓梯的動(dòng)態(tài)規(guī)劃過程

與回溯算法一樣，動(dòng)態(tài)規(guī)劃也使用“狀態(tài)”概念來表示問題求解的某個(gè)特定階段，每個(gè)狀態(tài)都對(duì)應(yīng)一個(gè)子問題以及相應(yīng)的局部最優(yōu)解。例如，爬樓梯問題的狀態(tài)定義為當(dāng)前所在樓梯階數(shù) $i$ 。

根據(jù)以上內(nèi)容，我們可以總結(jié)出動(dòng)態(tài)規(guī)劃的常用術(shù)語。

• 將數(shù)組 dp 稱為「$dp$ 表」，$dp[i]$ 表示狀態(tài) $i$ 對(duì)應(yīng)子問題的解。
• 將最小子問題對(duì)應(yīng)的狀態(tài)（即第 $1$ 和 $2$ 階樓梯）稱為「初始狀態(tài)」。
• 將遞推公式 $dp[i]=dp[i?1]+dp[i?2]$ 稱為「狀態(tài)轉(zhuǎn)移方程」。

空間優(yōu)化

細(xì)心的你可能發(fā)現(xiàn)，由于 $dp[i]$ 只與 $dp[i?1]$ 和 $dp[i?2]$ 有關(guān)，因此我們無須使用一個(gè)數(shù)組 dp 來存儲(chǔ)所有子問題的解，而只需兩個(gè)變量滾動(dòng)前進(jìn)即可。

climbing_stairs_dp.cpp

/* 爬樓梯：空間優(yōu)化后的動(dòng)態(tài)規(guī)劃 */
int climbingStairsDPComp(int n) {
    if (n == 1 || n == 2)
        return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}

觀察以上代碼，由于省去了數(shù)組 dp 占用的空間，因此空間復(fù)雜度從 $O(n)$ 降低至 $O(1)$ 。

在動(dòng)態(tài)規(guī)劃問題中，當(dāng)前狀態(tài)往往僅與前面有限個(gè)狀態(tài)有關(guān)，這時(shí)我們可以只保留必要的狀態(tài)，通過“降維”來節(jié)省內(nèi)存空間。這種空間優(yōu)化技巧被稱為“滾動(dòng)變量”或“滾動(dòng)數(shù)組”。