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

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

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

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

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

1 湊零錢問題

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

你可以認為每種硬幣的數(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ù)量
        int[] dp = new int[amount+1];
        //初始化
        for(int i = 0; i < amount+1; i++){
            dp[i] = amount+1;
            //最差的結果就是無數(shù)個1相加，那amount+1相當于無窮大。
            //代表-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];
    }
}