爬楼梯

一、题目

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

二、题解

题解一（枚举法，跟着题解写答案😶‍🌫️🤐😪😴😥🤩)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public int climbStairs(int n) {
       return switch (n) {
            case 1 -> 1;
            case 2 -> 2;
            case 3 -> 3;
            case 4 -> 5;
            case 5 -> 8;
            case 6 -> 13;
            case 7 -> 21;
            case 8 -> 34;
            case 9 -> 55;
            case 10 -> 89;
            case 11 -> 144;
            case 12 -> 233;
            case 13 -> 377;
            case 14 -> 610;
            case 15 -> 987;
            case 16 -> 1597;
            case 17 -> 2584;
            case 18 -> 4181;
            case 19 -> 6765;
            case 20 -> 10946;
            case 21 -> 17711;
            case 22 -> 28657;
            case 23 -> 46368;
            case 24 -> 75025;
            case 25 -> 121393;
            case 26 -> 196418;
            case 27 -> 317811;
            case 28 -> 514229;
            case 29 -> 832040;
            case 30 -> 1346269;
            case 31 -> 2178309;
            case 32 -> 3524578;
            case 33 -> 5702887;
            case 34 -> 9227465;
            case 35 -> 14930352;
            case 36 -> 24157817;
            case 37 -> 39088169;
            case 38 -> 63245986;
            case 39 -> 102334155;
            case 40 -> 165580141;
            case 41 -> 267914296;
            case 42 -> 433494437;
            case 43 -> 701408733;
            case 44 -> 1134903170;
            case 45 -> 1836311903;
            default -> 0;
        };
    }
}

img

image-20241216112755002

题解二（归纳总结法）

零级台阶 -> 0 0

一级台阶 -> 1 1

二级台阶 -> 2 1 - 1，2

三级台阶 -> 3 1 - 1 - 1，1 - 2，2 - 1

四级台阶 -> 5 1 - 1 - 1 - 1，1 - 1 - 2，1 -2 -1，2 - 1 - 1，2 - 2

五级台阶 -> 8 1 - 1 - 1 - 1 - 1，1 - 1 - 1 - 2，1 - 2 - 2，1 - 1 - 2 - 1，1 - 2 - 1 - 1，2 - 1 - 1 - 1，2 - 1 - 2，2 - 2 - 1

….

由上面我们可以归纳出

n级台阶 -> f(n-1) + f(n-2)

所以，f(n) = f(n-1) + f(n-2)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int climbStairs(int n){
    if (n <= 2) {
        return n;
    }
    // f(n) = f(n-1)+f(n-2)
    int result = 0;
    int n_1 = 2;
    int n_2 = 1;
    for (int i = 3; i <= n; i++) {
        result = n_1 + n_2;
        n_2 = n_1;
        n_1 = result;
    }
    return result;
}

image-20241216141930833

三、总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package com.loltoulan.dynamic_programming;

public class ClimbStairs {

    public static void main(String[] args) {
        System.out.println(climbStairs(5));
    }

    public static int climbStairs1(int n){
        return switch (n) {
            case 1 -> 1;
            case 2 -> 2;
            case 3 -> 3;
            case 4 -> 5;
            case 5 -> 8;
            case 6 -> 13;
            case 7 -> 21;
            case 8 -> 34;
            case 9 -> 55;
            case 10 -> 89;
            case 11 -> 144;
            case 12 -> 233;
            case 13 -> 377;
            case 14 -> 610;
            case 15 -> 987;
            case 16 -> 1597;
            case 17 -> 2584;
            case 18 -> 4181;
            case 19 -> 6765;
            case 20 -> 10946;
            case 21 -> 17711;
            case 22 -> 28657;
            case 23 -> 46368;
            case 24 -> 75025;
            case 25 -> 121393;
            case 26 -> 196418;
            case 27 -> 317811;
            case 28 -> 514229;
            case 29 -> 832040;
            case 30 -> 1346269;
            case 31 -> 2178309;
            case 32 -> 3524578;
            case 33 -> 5702887;
            case 34 -> 9227465;
            case 35 -> 14930352;
            case 36 -> 24157817;
            case 37 -> 39088169;
            case 38 -> 63245986;
            case 39 -> 102334155;
            case 40 -> 165580141;
            case 41 -> 267914296;
            case 42 -> 433494437;
            case 43 -> 701408733;
            case 44 -> 1134903170;
            case 45 -> 1836311903;
            default -> 0;
        };
    }

    public static int climbStairs(int n){
        if (n <= 2) {
            return n;
        }
        // f(n) = f(n-1)+f(n-2)
        int result = 0;
        int n_1 = 2;
        int n_2 = 1;
        for (int i = 3; i <= n; i++) {
            result = n_1 + n_2;
            n_2 = n_1;
            n_1 = result;
        }
        return result;
    }

}