C++DP問題特性

在上節(jié)中，我們學(xué)習(xí)了動態(tài)規(guī)劃是如何通過子問題分解來求解問題的。實際上，子問題分解是一種通用的算法思路，在分治、動態(tài)規(guī)劃、回溯中的側(cè)重點不同。

• 分治算法遞歸地將原問題劃分為多個相互獨(dú)立的子問題，直至最小子問題，并在回溯中合并子問題的解，最終得到原問題的解。
• 動態(tài)規(guī)劃也對問題進(jìn)行遞歸分解，但與分治算法的主要區(qū)別是，動態(tài)規(guī)劃中的子問題是相互依賴的，在分解過程中會出現(xiàn)許多重疊子問題。
• 回溯算法在嘗試和回退中窮舉所有可能的解，并通過剪枝避免不必要的搜索分支。原問題的解由一系列決策步驟構(gòu)成，我們可以將每個決策步驟之前的子序列看作為一個子問題。

實際上，動態(tài)規(guī)劃常用來求解最優(yōu)化問題，它們不僅包含重疊子問題，還具有另外兩大特性：最優(yōu)子結(jié)構(gòu)、無后效性。

最優(yōu)子結(jié)構(gòu)

我們對爬樓梯問題稍作改動，使之更加適合展示最優(yōu)子結(jié)構(gòu)概念。

如圖 14-6 所示，若第 $1$、$2$、$3$ 階的代價分別為 $1$、$10$、$1$ ，則從地面爬到第 $3$ 階的最小代價為 $2$ 。

圖 14-6   爬到第 3 階的最小代價

設(shè) $dp[i]$ 為爬到第 $i$ 階累計付出的代價，由于第 $i$ 階只可能從 $i?1$ 階或 $i?2$ 階走來，因此 $dp[i]$ 只可能等于 $dp[i?1]+cost[i]$ 或 $dp[i?2]+cost[i]$ 。為了盡可能減少代價，我們應(yīng)該選擇兩者中較小的那一個：

這便可以引出最優(yōu)子結(jié)構(gòu)的含義：原問題的最優(yōu)解是從子問題的最優(yōu)解構(gòu)建得來的。

本題顯然具有最優(yōu)子結(jié)構(gòu)：我們從兩個子問題最優(yōu)解 $dp[i?1]$ 和 $dp[i?2]$ 中挑選出較優(yōu)的那一個，并用它構(gòu)建出原問題 $dp[i]$ 的最優(yōu)解。

那么，上節(jié)的爬樓梯題目有沒有最優(yōu)子結(jié)構(gòu)呢？它的目標(biāo)是求解方案數(shù)量，看似是一個計數(shù)問題，但如果換一種問法：“求解最大方案數(shù)量”。我們意外地發(fā)現(xiàn)，雖然題目修改前后是等價的，但最優(yōu)子結(jié)構(gòu)浮現(xiàn)出來了：第 $n$ 階最大方案數(shù)量等于第 $n?1$ 階和第 $n?2$ 階最大方案數(shù)量之和。所以說，最優(yōu)子結(jié)構(gòu)的解釋方式比較靈活，在不同問題中會有不同的含義。

根據(jù)狀態(tài)轉(zhuǎn)移方程，以及初始狀態(tài) $dp[1]=cost[1]$ 和 $dp[2]=cost[2]$ ，我們就可以得到動態(tài)規(guī)劃代碼。

min_cost_climbing_stairs_dp.cpp

/* 爬樓梯最小代價：動態(tài)規(guī)劃 */
int minCostClimbingStairsDP(vector<int> &cost) {
    int n = cost.size() - 1;
    if (n == 1 || n == 2)
        return cost[n];
    // 初始化 dp 表，用于存儲子問題的解
    vector<int> dp(n + 1);
    // 初始狀態(tài)：預(yù)設(shè)最小子問題的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 狀態(tài)轉(zhuǎn)移：從較小子問題逐步求解較大子問題
    for (int i = 3; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

圖 14-7 展示了以上代碼的動態(tài)規(guī)劃過程。

圖 14-7   爬樓梯最小代價的動態(tài)規(guī)劃過程

本題也可以進(jìn)行空間優(yōu)化，將一維壓縮至零維，使得空間復(fù)雜度從 $O(n)$ 降低至 $O(1)$ 。

min_cost_climbing_stairs_dp.cpp

/* 爬樓梯最小代價：空間優(yōu)化后的動態(tài)規(guī)劃 */
int minCostClimbingStairsDPComp(vector<int> &cost) {
    int n = cost.size() - 1;
    if (n == 1 || n == 2)
        return cost[n];
    int a = cost[1], b = cost[2];
    for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = min(a, tmp) + cost[i];
        a = tmp;
    }
    return b;
}

無后效性?

無后效性是動態(tài)規(guī)劃能夠有效解決問題的重要特性之一，定義為：給定一個確定的狀態(tài)，它的未來發(fā)展只與當(dāng)前狀態(tài)有關(guān)，而與當(dāng)前狀態(tài)過去所經(jīng)歷過的所有狀態(tài)無關(guān)。

以爬樓梯問題為例，給定狀態(tài) $i$ ，它會發(fā)展出狀態(tài) $i+1$ 和狀態(tài) $i+2$ ，分別對應(yīng)跳 $1$ 步和跳 $2$ 步。在做出這兩種選擇時，我們無須考慮狀態(tài) $i$ 之前的狀態(tài)，它們對狀態(tài) $i$ 的未來沒有影響。

然而，如果我們向爬樓梯問題添加一個約束，情況就不一樣了。

例如圖 14-8 ，爬上第 $3$ 階僅剩 $2$ 種可行方案，其中連續(xù)三次跳 $1$ 階的方案不滿足約束條件，因此被舍棄。

圖 14-8   帶約束爬到第 3 階的方案數(shù)量

在該問題中，如果上一輪是跳 $1$ 階上來的，那么下一輪就必須跳 $2$ 階。這意味著，下一步選擇不能由當(dāng)前狀態(tài)（當(dāng)前樓梯階數(shù)）獨(dú)立決定，還和前一個狀態(tài)（上輪樓梯階數(shù)）有關(guān)。

不難發(fā)現(xiàn)，此問題已不滿足無后效性，狀態(tài)轉(zhuǎn)移方程 $dp[i]=dp[i?1]+dp[i?2]$ 也失效了，因為 $dp[i?1]$ 代表本輪跳 $1$ 階，但其中包含了許多“上一輪跳 $1$ 階上來的”方案，而為了滿足約束，我們就不能將 $dp[i?1]$ 直接計入 $dp[i]$ 中。

為此，我們需要擴(kuò)展?fàn)顟B(tài)定義：狀態(tài) $[i,j]$ 表示處在第 $i$ 階、并且上一輪跳了 $j$ 階，其中 $j\in \{1,2\}$ 。此狀態(tài)定義有效地區(qū)分了上一輪跳了 $1$ 階還是 $2$ 階，我們可以據(jù)此來決定下一步該怎么跳。

• 當(dāng) $j$ 等于 $1$ ，即上一輪跳了 $1$ 階時，這一輪只能選擇跳 $2$ 階。
• 當(dāng) $j$ 等于 $2$ ，即上一輪跳了 $2$ 階時，這一輪可選擇跳 $1$ 階或跳 $2$ 階。

如圖 14-9 所示，在該定義下，$dp[i,j]$ 表示狀態(tài) $[i,j]$ 對應(yīng)的方案數(shù)。此時狀態(tài)轉(zhuǎn)移方程為：

圖 14-9   考慮約束下的遞推關(guān)系

最終，返回 $dp[n,1]+dp[n,2]$ 即可，兩者之和代表爬到第 $n$ 階的方案總數(shù)。

climbing_stairs_constraint_dp.cpp

/* 帶約束爬樓梯：動態(tài)規(guī)劃 */
int climbingStairsConstraintDP(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 初始化 dp 表，用于存儲子問題的解
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    // 初始狀態(tài)：預(yù)設(shè)最小子問題的解
    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[2][1] = 0;
    dp[2][2] = 1;
    // 狀態(tài)轉(zhuǎn)移：從較小子問題逐步求解較大子問題
    for (int i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
    }
    return dp[n][1] + dp[n][2];
}

在上面的案例中，由于僅需多考慮前面一個狀態(tài)，我們?nèi)匀豢梢酝ㄟ^擴(kuò)展?fàn)顟B(tài)定義，使得問題重新滿足無后效性。然而，某些問題具有非常嚴(yán)重的“有后效性”。

在這個問題中，下次跳躍依賴于過去所有的狀態(tài)，因為每一次跳躍都會在更高的階梯上設(shè)置障礙，并影響未來的跳躍。對于這類問題，動態(tài)規(guī)劃往往難以解決。

實際上，許多復(fù)雜的組合優(yōu)化問題（例如旅行商問題）都不滿足無后效性。對于這類問題，我們通常會選擇使用其他方法，例如啟發(fā)式搜索、遺傳算法、強(qiáng)化學(xué)習(xí)等，從而在有限時間內(nèi)得到可用的局部最優(yōu)解。