代码随想录算法训练营第三十二天-509斐波那契数、70爬楼梯、746使用最小花费爬楼梯

前言
状态：动态规划之前没有接触过，基本都不会。看了前面两题 746 按照解题方法 AC 了。
更新

1	24-06-18 初始记录

初步题解

509 斐波那契数

题目链接：(https://leetcode.cn/problems/fibonacci-number)

// 递归做法
public int fib(int n) {  
    if (n == 0) {  
        return 0;  
    }  
    if (n == 1) {  
        return 1;  
    }  
  
    return fib(n - 1) + fib(n - 2);  
}

70 爬楼梯

题目链接：(https://leetcode.cn/problems/climbing-stairs/)

不会。

746 使用最小花费爬楼梯

题目链接：(https://leetcode.cn/problems/min-cost-climbing-stairs/)

确定 dp[i] 的含义：爬到 i 台阶需要的最小花费
递推公式：Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
dp 数组的初始化 dp[0] = 0、dp[1] = 1
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public static void main(String[] args) {  
    int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};  
    minCostClimbingStairs(cost);  
}  
public static int minCostClimbingStairs(int[] cost) {  
    int[] dp = new int[cost.length + 1];  
    dp[0] = 0;  
    dp[1] = 0;  
  
    for (int i = 2; i < dp.length; i++) {  
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[cost.length];  
}

看解析

509 斐波那契数

题解：(https://programmercarl.com/0509.斐波那契数.html)

确定 dp[i] 的含义：第 i 个斐波那契数
递推公式：dp[i] = dp[i - 1] + dp[i - 2]
dp 数组的初始化 dp[0] = 1、dp[1] = 1
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public static int fibBp(int n) {  
    if (n <= 1) {  
        return n;  
    }  
    int[] dp = new int[n + 1];  
    dp[0] = 0;  
    dp[1] = 1;  
    for (int i = 2; i <= n; i++) {  
        dp[i] = dp[i - 1] + dp[i - 2];  
    }  
  
    System.out.println(Arrays.toString(dp));  
  
    return dp[n];  
}
// 只维护两个数值的版本
public int fib(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    int[] dp = new int[2];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2 ; i < n+1 ; i++){
        int sum  = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum;
    }
    return dp[1];
}

70 爬楼梯

解析：(https://programmercarl.com/0070.爬楼梯.html)

确定 dp[i] 的含义：爬 i 阶有几种方法
递推公式：dp[i] = dp[i - 1] + dp[i - 2]这里有点难理解：因为走到 i 阶只有两种情况，1️⃣从 i - 2 到 i 走两步；2️⃣从 i - 1 到 i 走两步。所以到 i 阶的总方法数 : dp[i] = dp[i - 1] + dp[i - 2]
dp 数组的初始化 dp[1] = 1、dp[2] = 2。根据题目描述，n > 0 所以这里这么设置。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

public int climbStairs(int n) {  
    if (n <= 2) {  
        return n;  
    }  
  
    int[] dp = new int[n + 1];  
    dp[1] = 1;  
    dp[2] = 2;  
    for (int i = 3; i <= n; i++) {  
        dp[i] = dp[i - 1] + dp[i - 2];  
    }  
  
    return dp[n];  
}

746 使用最小花费爬楼梯

解析：(https://programmercarl.com/0746.使用最小花费爬楼梯.html)