算法训练Day38|● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

 1// 利用公式推导
 2class Solution {
 3    public int fib(int n) {
 4        if (n < 2) return n; // 前两个数值
 5        int a = 0, b = 1, c = 0; 
 6        for (int i = 1; i < n; i++) {
 7            c = a + b; // 公式
 8            a = b; // 递归下去
 9            b = c; 
10        }
11        return c;
12    }
13}
14
15// 递归
16class Solution {
17    public int fib(int n) {
18        if (n < 2) return n;
19        return fib(n - 1) + fib(n - 2);
20    }
21}
22
23// 动规
24class Solution {
25    public int fib(int n) {
26
27
28        // 确定dp数组及下标的含义，dp[i]的定义：第i个数的斐波那契数列值是dp[i]
29        if (n < 2) {
30            return n;
31        }
32
33        // dp数组的初始化
34        int[] dp = new int[n + 1];
35        dp[0] = 0;
36        dp[1] = 1;
37
38        // 确定递推公式
39        // 确定遍历顺序，递推公式显示从前向后遍历
40        // 举例推导dp数组
41        for (idx = 2; idx <= n; idx++) {
42
43            dp[n] = dp[n - 1] + dp[n - 2];
44        }
45        return dp[n];
46    }
47}

 1// 动规
 2class Solution {
 3    public int climbStairs(int n) {
 4        if (n <= 2) return n;
 5        int[] dp = new int[n + 1];
 6
 7        dp[0] = 0;
 8        dp[1] = 1;
 9        dp[2] = 2;
10        for (int i = 3; i <= n; i++) {
11            dp[i] = dp[i - 1] + dp[i - 2];
12        }
13        return dp[n];
14    }
15}
16// 递归
17class Solution {
18    public int climbStairs(int n) {
19        if (n <= 2) return n;
20
21        return climbStairs(n - 1) + climbStairs(n - 2);
22    }
23}

 1class Solution {
 2    public int minCostClimbingStairs(int[] cost) {
 3        // 确定递推数组及初始化
 4        int[] dp = new int[cost.length + 1];
 5        dp[0] = 0;
 6        dp[1] = 0;
 7        // 遍历顺序，从前向后
 8        for (int i = 2; i <= cost.length; i++) {
 9            // 递推公式
10            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
11        }
12        return dp[cost.length];
13    }
14}