動(dòng)態(tài)規(guī)劃理論基礎(chǔ)

解題模版：動(dòng)規(guī)五部曲

1. 確定dp數(shù)組下標(biāo)的含義
2. 確定遞推公式
3. 確定初始值
4. 確定遍歷順序
5. 舉例推到

最好將每一步打印下來(lái)。

斐波那契數(shù)

力扣題目鏈接

var fib = function(n) {
    let dp=[]
    dp[0]=0
    dp[1]=1

    for(let i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

爬樓梯

力扣題目鏈接

var climbStairs = function(n) {
    let dp=[]
    dp[0]=0
    dp[1]=1;
    dp[2]=2;
    for(let i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

使用最小花費(fèi)爬樓梯

力扣題目鏈接
自己的分析：

1. dp 數(shù)組：到達(dá)第i梯的最低花費(fèi)
2. 狀態(tài)轉(zhuǎn)移方程： dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. 初始狀態(tài)： dp[0] dp[1] 均為0，不需要花銷(xiāo)
4. 遍歷順序：順序
   bingo！

var minCostClimbingStairs = function(cost) {
    let dp = [];
    // dp[i] 到達(dá)第i梯的最低花費(fèi)
    dp[0] = 0;
    dp[1] = 0;
    for (let i = 2; i <= cost.length; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
  return dp[dp.length - 1];
};