動態(tài)規(guī)劃問題的一般形式就是求最值。最顯著的特點是最優(yōu)子結(jié)構(gòu)和重疊子問題。最優(yōu)子結(jié)構(gòu)就是子問題的最優(yōu)解，可以從子問題的最優(yōu)結(jié)果推出更大規(guī)模問題的最優(yōu)結(jié)果，可以用狀態(tài)轉(zhuǎn)移方程描述問題。重疊子問題可以通過創(chuàng)建備忘錄dp[]避免重復(fù)計算。
零錢兌換的解題步驟：
1）先確定狀態(tài)，也就是原問題和子問題中變化的變量，由于硬幣數(shù)量可以無限，所以唯一確定的狀態(tài)就是目標金額amount。
2）然后確定dp函數(shù)的定義，當前的目標金額是n，至少需要dp(n)個硬幣湊出該金額。
3）確定選擇并擇優(yōu)，無論當前的目標金額是多少，選擇就是從面額列表coins中選則一個硬幣，然后目標金額就會減少。
4）最后明確遞歸的終止條件，顯然目標金額為0時，所需硬幣數(shù)量為0，而當目標金額小于0時，無解。在動態(tài)規(guī)劃中體現(xiàn)為子問題無解，跳過該次內(nèi)層循環(huán)。
湊零錢問題的狀態(tài)轉(zhuǎn)移方程如下：

[dp(n)=egin{cases}
0 & n=0 \
-1 & n<0 \
min{dp[n-coin]+1 | coinin coins} & n>0
end{cases}]

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        for(int i = 0; i < dp.size(); i++)
        {
            for(int coin : coins)
            {
                if(i-coin < 0)
                    continue;
                dp[i] = min(dp[i], 1+dp[i-coin]);//索引為i-coin的dp[i-coin]加上for循環(huán)在這次選出的這個coin（即加1）

            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];//為什么要這樣返回？？當給的coins不能湊出amount時就會出錯，比如coins=[2],amount=3,amount無法湊出，此時應(yīng)返回-1
    }

總結(jié)

以上是生活随笔為你收集整理的动态规划解题（leetcode322零钱兑换）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。