Day 38 | 动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯

动态规划理论基础

讲解：https://www.bilibili.com/video/BV13Q4y197Wg

什么是动态规划

1. 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

2. 所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

   解题步骤

3. 确定dp数组（dp table）以及下标的含义

4. 确定递推公式
5. dp数组如何初始化
6. 确定遍历顺序
7. 举例推导dp数组

Leetcode 509.斐波那契数

题目：509.斐波那契数

初始思路

动态规划入门题目

代码

// 暴力递归
var fib = function (n) {
    if (n == 0) return 0
    if (n == 1) return 1
    return fib(n - 1) + fib(n - 2)
};

// 动态规划解法
var fib = function (n) {
    if (n <= 1) return n
    const dp = [0, 1]
    for (let i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

// 滚动数组优化
// 动规状态转移中，当前结果只依赖前两个元素的结果，所以只要两个变量代替dp数组记录状态过程。将空间复杂度降到O(1)
var fib = function (n) {
    if (n <= 1) return n
    let prev2 = 0
    let prev1 = 1
    let result = 0
    for (let i = 2; i <= n; i++){
        result = prev1 + prev2
        prev2 = prev1
        prev1 = result
    }
    return result
}

感想

1. 确定dp数组以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2. 确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
3. dp数组如何初始化：dp[0]=0 dp[1]=1
4. 确定遍历顺序：从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
5. 举例推导dp数组：0 1 1 2 3 5 8 13 21 34 55

Leetcode 70.爬楼梯

题目：70.爬楼梯

初始思路

属于是一开始看没啥思路，看明白之后发现就是斐波那契数列

代码

var climbStairs = function (n) {
    // dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
    // dp[i] = dp[i - 1] + dp[i - 2]
    let dp = [1, 2]
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n - 1]
};

// 滚动数组优化
var climbStairs = function (n) {
    let prev = 1;
    let cur = 1;
    for (let i = 2; i < n + 1; i++) {
        [prev, cur] = [cur, prev + cur]
        // const temp = cur;   // 暂存上一次的cur
        // cur = prev + cur;   // 当前的cur = 上上次cur + 上一次cur
        // prev = temp;        // prev 更新为 上一次的cur
    }
    return cur;
}

感想

1. 确定dp数组以及下标的含义：dp[i]： 爬到第i层楼梯，有dp[i]种方法
2. 从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
   首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
   还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
   那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！所以dp[i] = dp[i - 1] + dp[i - 2] 。
3. dp数组如何初始化：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
4. 确定遍历顺序：从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
5. 举例推导dp数组：就是斐波那契数列

Leetcode 746.使用最小花费爬楼梯

题目：746.使用最小花费爬楼梯

初始思路

相比于爬楼梯需要考虑最小花费

代码

var minCostClimbingStairs = function (cost) {
    const dp = [cost[0], cost[1]]
    for (let i = 2; i < cost.length; i++){
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
    }
    //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
    return Math.min(dp[cost.length - 1], dp[cost.length - 2])
};

感想

1. 确定dp数组以及下标的含义：dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）
2. 确定递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
   那么究竟是选dp[i-1]还是dp[i-2]呢？一定是选最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
   注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值
3. dp数组如何初始化：
4. 确定遍历顺序：从前往后遍历cost就可以了
5. 举例推导dp数组：