1. question: 爬楼梯（简单）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/climbing-stairs
示例 1：
1
2
3
4
5
| 输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
| 输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
提示：
2. answers
这道题最开始想的是回溯法。因为每一级阶梯，都有两种选择。因此可采用回溯法，但是回溯法本质上就是遍历，在LeetCode最后两个测试用例上超时了，代码如下所示：
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
| public class Solution_0112 {
public int method = 0;
public void recur(int n, int step) {
if(step == n) {
method += 1;
return;
}
if(step > n) return;
for (int i = 1; i <= 2; i++) {
step += i;
recur(n, step);
step -= i;
}
}
public int climbStairs(int n) {
recur(n, 0);
return method;
}
public static void main(String[] args) {
System.out.println();
Solution_0112 s = new Solution_0112();
System.out.println(s.climbStairs(6));
}
}
|
后来，试着写了前几个阶梯的方法数量，发现，和斐波那契数列一样，M(n) = M(n-1) + M(n-2)。仔细分析，可以发现如下规律：
- 在n-1级阶梯，可一次性迈一步到达n阶梯。（到达n-1级阶梯有多少种方法，那么到达n级阶梯就有多少种方法）
- 在n-2级阶梯，可一次性迈两步到达n阶梯。（到达n-2级阶梯有多少种方法，那么到达n级阶梯就有多少种方法）
那么为什么n-2级阶梯，不能迈两次一步呢？因为迈一次一步，就到达n-1级阶梯了，此时属于情况一。对于n-3级阶梯同理，无论怎么迈，都是n-1或者n-2的情况。
因此，代码如下所示：
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
| public class Solution_0112_03 {
public int climbStairs(int n) {
if(n <= 2) return n;
int pre = 1;
int post = 2;
int thisStairs = 0;
for (int i = 3; i <= n; i++) {
thisStairs = pre + post;
pre = post;
post = thisStairs;
}
return thisStairs;
}
public static void main(String[] args) {
System.out.println();
Solution_0112_03 s = new Solution_0112_03();
System.out.println(s.climbStairs(5));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
