代码随想录算法训练营第33天|LeetCode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

1. LeetCode 509. 斐波那契数

题目链接：https://leetcode.cn/problems/fibonacci-number/
文章链接：https://programmercarl.com/0509.斐波那契数.html
视频链接：https://www.bilibili.com/video/BV1f5411K7mo

思路：
动态规划步骤如下：

1. 定义dp数组
   int[] dp = new int[n+1];
2. 递推公式
   dp[i] = dp[i-1] + dp[i-2];
3. 初始化
   dp[0] = 0;
   dp[1] = 1;
4. 遍历顺序 从前往后

解法：
class Solution {
    public int fib(int n) {
        if (n==0 || n==1) {
            return n;
        }
        // 定义dp数组
        int[] dp = new int[n+1];

        //递推公式
        //dp[i] = dp[i-1] + dp[i-2];

        // 初始化
        dp[0] = 0;
        dp[1] = 1;

        // 遍历顺序 从前往后
        for (int i = 2;i < n+1;i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

2. LeetCode 70. 爬楼梯

题目链接：https://leetcode.cn/problems/climbing-stairs/description/
文章链接：https://programmercarl.com/0070.爬楼梯.html
视频链接：https://www.bilibili.com/video/BV17h411h7UH

思路：
解题关键是要理解：
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
至于为什么不考虑第一层连续跨两个一层到达第三层这个方式，是因为该方式包含在从第二层跨一层到达第三层的方式里面。
动态规划步骤如下：

1. 定义dp数组 dp[i]表示爬到第i层楼梯，有dp[i]种方法
   int[] dp = new int[n+1];
2. 递推公式
   dp[i] = dp[i-1] + dp[i-2];
3. 初始化
   dp[1] = 1;
   dp[2] = 2;
4. 遍历顺序 从前往后遍历
   注意：本题中n>=1，所以不需要考虑n=0的初始化情况。

解法：
class Solution {
    public int climbStairs(int n) {
        if (n<=2) return n;
        //1. 定义dp数组 dp[i]表示爬到第i层楼梯，有dp[i]种方法
        int[] dp = new int[n+1];
        //2. 递推公式
        //dp[i] = dp[i-1] + dp[i-2];
        //3.初始化
        dp[1] = 1;
        dp[2] = 2;
        //4.遍历顺序 从前往后遍历
        for (int i=3;i<=n;i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

3. LeetCode 746. 使用最小花费爬楼梯

题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
文章链接：https://programmercarl.com/0746.使用最小花费爬楼梯.html#算法公开课
视频链接：https://www.bilibili.com/video/BV16G411c7yZ/

思路：

1. 定义dp数组 dp[i]表示到达第i层最低花费
   int[] dp=new int[cost.length+1];
2. 递推公式
   dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3. 初始化
   dp[0]=0;
   dp[1]=0;
4. 遍历顺序 从前往后
   注意：只有爬楼梯时才会消耗费用，即dp[i]+cost[i]，当处在某层时不消耗费用，即dp[i]。故由于可以选择从0或1下标开始爬楼梯，当处在0和1下标的楼层时，并没有消耗费用，此时初始化为0。

解法：
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        
        //1.定义dp数组 dp[i]表示到达第i层最低花费
        int[] dp=new int[cost.length+1];
        //2.递推公式
        //dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        //3.初始化
        dp[0]=0;
        dp[1]=0;
        //4.遍历顺序 从前往后
        for (int i=2;i<=cost.length;i++) {
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[cost.length];
    }
}