一文详解爬楼梯

Leetcode链接
这个题的本质是
q[3] = q[1] + q[2];
q[4] = q[2] + q[3];
q[5] = q[4] + q[3];
…
为什么是这样呢，你从第n阶来看，你只能从第n-1阶级或者第n-2阶级上来，因此你每次只能走1步或者两步。

因此可以由两种方法：
方法一

public int climbStairs(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        int a = 1; // 表示第 n - 2 个台阶的走法
        int b = 2;// 表示第 n - 1 个台阶的走法
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法2：

public int climbStairs2(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return climbStairs2(n-1) + climbStairs2(n-2);
    }
1
2
3
4
5
6

采用递归的话会出现重复计算，你计算n - 1步时，n-2其实你已经计算过了。所以会出现重复计算的结果。因此推荐代码1.