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

509. 斐波那契数

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

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

题解：

public int fib(int n) {// 如果 n 是 0，直接返回 0if (n == 0) {return 0;}// 如果 n 是 1，直接返回 1if (n == 1) {return 1;}// 创建一个数组来存储斐波那契数列的计算结果int[] dp = new int[n + 1];// 初始化第一个斐波那契数为 0dp[0] = 0;// 初始化第二个斐波那契数为 1dp[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];
}