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

509. 斐波那契数

题目链接：509. 斐波那契数
文档讲解：代码随想录
状态：so easy

思路：最简单的递归就不说了。使用动态规划的话，状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

题解：

public int fib(int n) {
    // 如果 n 是 0，直接返回 0
    if (n == 0) {
        return 0;
    }
    // 如果 n 是 1，直接返回 1
    if (n == 1) {
        return 1;
    }
    // 创建一个数组来存储斐波那契数列的计算结果
    int[] dp = new int[n + 1];
    // 初始化第一个斐波那契数为 0
    dp[0] = 0;
    // 初始化第二个斐波那契数为 1
    dp[1] = 1;
    // 从第三个数开始计算，每个数都是前两个数之和
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回第 n 个斐波那契数
    return dp[n];
}

70. 爬楼梯

题目链接：70. 爬楼梯
文档讲解：代码随想录
状态：还行

思路：第n节台阶可以是第n-1节台阶走一步，也可以通过第n-2节台阶走两步到达，所以状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]
注意：dp[i]的含义是到达第i节台阶有几种方案，而不是有多少步！！！

题解：

public int climbStairs(int n) {
    // 如果只有 1 级台阶，只有一种方法可以到达，即一步跨上去
    if (n == 1) {
        return 1;
    }
    // 创建一个数组来存储每一级台阶的不同走法
    int[] dp = new int[n + 1];
    // 初始化第 1 级台阶的走法，只有一种走法
    dp[1] = 1;
    // 初始化第 2 级台阶的走法，有两种走法：每次跨一级，或者一次跨两级
    dp[2] = 2;
    // 从第 3 级台阶开始计算，每一级台阶的走法是前两级台阶走法之和
    // 因为到达该级台阶的最后一步可以是从前一级台阶跨一步，或者从前二级台阶跨两步
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回第 n 级台阶的走法总数
    return dp[n];
}

746. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯
文档讲解：代码随想录
状态：还行

动态规划状态转移方程：

到达第 i 级台阶有两种选择：

1. 从第 i-2 级台阶跨两步到达第 i 级台阶，花费为 dp[i-2] + cost[i-2]。
2. 从第 i-1 级台阶跨一步到达第 i 级台阶，花费为 dp[i-1] + cost[i-1]。

因此，dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])。

初始化：

由于可以从第 0 级台阶或第 1 级台阶开始，不需要花费，因此 dp[0] = 0 和 dp[1] = 0。

题解：

public int minCostClimbingStairs(int[] cost) {
    // 创建一个数组 dp 来存储到达每一级台阶的最小花费
    int[] dp = new int[cost.length + 1];
    // 初始化 dp[0] 和 dp[1]，因为开始可以从第 0 级或第 1 级台阶开始，不需要花费
    dp[0] = 0;
    dp[1] = 0;
    
    // 从第 2 级台阶开始计算每一级台阶的最小花费
    for (int i = 2; i <= cost.length; i++) {
        // 到达第 i 级台阶有两种选择：
        // 1. 从第 i-2 级台阶跨两步到达第 i 级台阶，花费为 dp[i-2] + cost[i-2]
        // 2. 从第 i-1 级台阶跨一步到达第 i 级台阶，花费为 dp[i-1] + cost[i-1]
        // 取这两种选择中的最小值作为到达第 i 级台阶的最小花费
        dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
    }
    
    // 返回到达最后一级台阶的最小花费
    return dp[cost.length];
}