首先要判斷一道題是否是動態(tài)規(guī)劃

1. 一般動態(tài)規(guī)劃是求最值（但也不是百分之百）
2. 最優(yōu)子結(jié)構(gòu)
   一般會通過子問題的最值得到原問題的答案
3. 窮舉
4. 狀態(tài)轉(zhuǎn)移方程
5. 重疊 子問題
   由于暴力求解效率低，所以需要備忘錄或者DP table來優(yōu)化窮舉過程

下面是重點，思維框架

明確 base case -> 明確「狀態(tài)」-> 明確「選擇」 -> 定義 dp 數(shù)組/函數(shù)的含義。

以coinChange為例

1. base case
2. 狀態(tài)（也就是變量）
   原問題和子問題中變化的變量（目標(biāo)金額amount，因為目標(biāo)金額會不斷的向最終結(jié)果靠近）
3. 選擇，也就是導(dǎo)致狀態(tài)產(chǎn)生變化的行為
   目標(biāo)金額為什么會變化呢，因為在選擇硬幣，沒選擇一枚硬幣，金額就更靠近我們的目標(biāo)金額。所以所有硬幣的面值就是選擇。
4. 確定dp函數(shù)/dp數(shù)組的定義
   自頂向下，一般自頂向下的解法是一個遞歸的dp函數(shù)，一般來說函數(shù)的參數(shù)就是狀態(tài)轉(zhuǎn)移中會變化的量，也就是上面說的狀態(tài)，函數(shù)的返回值就是題目要求我們的計算的量，

function coinChange (coins, amount) {
    const memo = [];
    function dp (n) {
        if (n === 0) return 0;
        if (n < 0) return -1;
        if (memo[n] !== undefined) return memo[n];
        let res = Infinity;
        for (const coin of coins) {
            const sub = dp(n - coin);
            memo[n - coin] = sub;
            if (sub === -1) continue;
            res = Math.min(res, sub + 1);
        }
        if (res === Infinity) return -1;
        return res;
    }

    return dp(amount);
}

function coinChange (coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let n = 0; n < amount+1; n++ ) {
        for (const coin of coins) {
            if (n - coin < 0) continue;
            dp[n] = Math.min(dp[n], dp[n - coin] + 1);
        }
    }
    return (dp[amount] === amount + 1) ? -1 : dp[amount];
}