1，问题描述
70. 爬楼梯
难度：简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 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，初步思考
这个题目本身就是斐波那契数列，直接递归、动态规划秒了
3，代码处理
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
| import java.util.HashMap;
import java.util.Map;
public class _70爬楼梯 {
public int climbStairs_dp(int n) {
if (n <= 2) return n;
int before = 1, cur = 2, idx = 3;
while (idx <= n) {
int temp = before + cur;
before = cur;
cur = temp;
idx++;
}
return cur;
}
public int climbStairs_recursion(int n) {
if (n <= 1) {
return 1;
}
if (map.containsKey(n)) return map.get(n);
int cur = climbStairs_recursion(n - 1) + climbStairs_recursion(n - 2);
map.put(n, cur);
return cur;
}
private Map<Integer, Integer> map = new HashMap<>();
public static void main(String[] args) {
System.out.println(new _70爬楼梯().climbStairs_recursion(3));
System.out.println(new _70爬楼梯().climbStairs_recursion(2));
}
}
|