知乎一篇高贊動(dòng)態(tài)規(guī)劃
《labuladong的算法小抄-動(dòng)態(tài)規(guī)劃章節(jié)》

動(dòng)態(tài)規(guī)劃應(yīng)用比較多的情況是求最值。核心問題是窮舉。
首先動(dòng)態(tài)規(guī)劃三要素：
1.記憶數(shù)組/重疊子問題。
2.最優(yōu)子結(jié)構(gòu)。
3.狀態(tài)轉(zhuǎn)移方程。

對(duì)于記憶數(shù)組，我想說的是，最傳統(tǒng)的遞歸暴力解法會(huì)有很多的重復(fù)計(jì)算，最終的結(jié)果以來歷史計(jì)算的結(jié)果，那動(dòng)態(tài)規(guī)劃就可以減少重復(fù)計(jì)算。

最優(yōu)子結(jié)構(gòu)：首先要符合最優(yōu)子結(jié)構(gòu)，子問題必須相互獨(dú)立。例如我們接下來的每個(gè)例題都會(huì)分析是否能用動(dòng)態(tài)規(guī)劃來做，在湊零錢問題中，硬幣數(shù)量沒有限制，任何子問題都沒有限制，互相獨(dú)立。分享一個(gè)例子：你參加考試，你的原問題是考出最高的總成績(jī)，那么你的子問題就是把各科成績(jī)都考到最高分，各科最高分那你的每道題都是最高分。。。。最終結(jié)果就是滿分。那這個(gè)問題符合最優(yōu)子結(jié)構(gòu)，每門課程考到最高分，這些子問題互相獨(dú)立、互不干擾。但如果有個(gè)條件，你的語文數(shù)學(xué)成績(jī)相互制約，數(shù)學(xué)成績(jī)高，就會(huì)語文低，那就會(huì)子問題不獨(dú)立，各科無法同時(shí)達(dá)到最優(yōu)解。

做題步驟：
1.定義數(shù)組（很重要），dp[i]含義。
2.找出數(shù)組元素關(guān)系式，這里我分享自己的思路就是，一般都是第n個(gè)結(jié)果是什么，那第n個(gè)結(jié)果之前的結(jié)果是什么，這往往是我做題中的破題之處。例如：斐波那契數(shù)列，dp[n] = dp[n-1] + dp[n-2];矩陣從左上角到右下角，求最大值，那到右下角前會(huì)經(jīng)過哪里？；湊零錢問題，在得到最少的硬幣個(gè)數(shù)dp[n]之前，得到dp[n]= min(dp[n-coin]+1 ,dp[n]);coin表示硬幣面值，n表示需要湊的金額。
3.base case最簡(jiǎn)單案例，初始化。

1 湊零錢問題

給你一個(gè)整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個(gè)整數(shù) amount ，表示總金額。
計(jì)算并返回可以湊成總金額所需的 最少的硬幣個(gè)數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認(rèn)為每種硬幣的數(shù)量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2

class Solution {
    public int coinChange(int[] coins, int amount) {
        //定義數(shù)組，amount == i 的時(shí)候最少的硬幣數(shù)量
        int[] dp = new int[amount+1];
        //初始化
        for(int i = 0; i < amount+1; i++){
            dp[i] = amount+1;
            //最差的結(jié)果就是無數(shù)個(gè)1相加，那amount+1相當(dāng)于無窮大。
            //代表-1，表示無解
        }
        dp[0] = 0;
        //開始循環(huán)
        for(int i = 1; i < amount+1; i++){
            for(int j = 0; j < coins.length; j++){
                if(i - coins[j] < 0) continue;
                dp[i] = Math.min(dp[i], 1 + dp[i-coins[j]]);
            }
        }
        return (dp[amount] == amount+1)?-1: dp[amount];
    }
}