背包問(wèn)題是動(dòng)態(tài)規(guī)劃中的經(jīng)典題型之一，需要反復(fù)咀嚼，感受它的魅力。本文以L(fǎng)eetCode 512 零錢(qián)兌換II為例進(jìn)行講解：

image.png

思路

1. 對(duì)于動(dòng)態(tài)規(guī)劃類(lèi)題目首先要分析題目中有哪幾種狀態(tài)和選擇。以零錢(qián)兌換II為例，狀態(tài)有兩種：硬幣面值種類(lèi)和金額大小。選擇也有兩種：當(dāng)前的硬幣是否“放入”金額這個(gè)容器內(nèi)（放或者不放）。
2. 然后確定數(shù)組的含義，這一步至關(guān)重要，不同的含義會(huì)導(dǎo)致后面的操作完全不一樣。本題是計(jì)算用所給不同面值的硬幣湊成當(dāng)前金額的方式有多少種，所以數(shù)組定義為在使用前種面值的硬幣時(shí)，總共有多少種方式可以湊出當(dāng)前金額。
   每當(dāng)“物品”要放入到“金額”這個(gè)口袋中時(shí)，有兩種情況：

• 當(dāng)口袋的剩余容量不小于物品的重量（硬幣的價(jià)值），有兩種操作方式：選擇放入或者選擇不放入。
• 當(dāng)口袋的剩余容量小于物品的重量（隱蔽的價(jià)值），此時(shí)只能選擇不放入。
  根據(jù)以上兩種情況，可以寫(xiě)出相關(guān)的偽代碼：

if (j > coins[i])
    選擇將當(dāng)前面值的硬幣放入金額口袋
    或者
    選擇不將當(dāng)前面值的硬幣放入金額口袋
else
    只有一種選擇，不將當(dāng)前面值的硬幣放入金額口袋

3. 思考狀態(tài)轉(zhuǎn)移

• 將第種硬幣放入剩余容量為的口袋內(nèi)時(shí)，此時(shí)的結(jié)果取決于第種硬幣放入剩余容量為的口袋內(nèi)的組合數(shù)，即
• 不將第種硬幣放入剩余容量為的口袋內(nèi)時(shí)，此時(shí)的結(jié)果取決于上一種硬幣放入剩余容量為的口袋內(nèi)的組合數(shù)，即
• 當(dāng)前口袋容量不小于當(dāng)前硬幣面值時(shí)，有兩種可能的操作，所以此時(shí)的
• 當(dāng)前口袋容量小于當(dāng)前硬幣面值時(shí)，只能有一種“不放回”操作，所以此時(shí)的

4. 邊界條件
   一般情況下，狀態(tài)有幾種就需要考慮幾種邊界條件。當(dāng)硬幣面值的種類(lèi)數(shù)為0時(shí)，對(duì)于任意非0金額口袋肯定是裝不滿(mǎn)的。當(dāng)金額口袋容量為0時(shí)，我們不需要任何操作就相當(dāng)于裝滿(mǎn)了這個(gè)口袋。

##邊界條件
for (int i=0; i<=n; i++)
  dp[i][0] = 1;
for (int i =0; i<=amount; i++)
  dp[0][i] = 0;

5. 編寫(xiě)代碼

int change(int amount, vector<int>& coins) {
        int n = coins.size();
        if (amount == 0 && n == 0) return 1;
        vector<vector<int>>dp(n+1, vector<int>(amount+1));
        for (int i=0; i<n+1; i++)
            dp[i][0] = 1;
        //vector自動(dòng)初始化為0，所以這里不再需要重復(fù)賦值來(lái)晚上邊界條件
        // for (int i=0; i<=amount; i++)
        //     dp[0][i] = 0;
        for (int i=1; i<n+1; i++){
            for (int j=1; j<=amount; j++){
                if (j - coins[i-1] >=0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][amount];

    }