题目描述
假设你正在爬楼梯。需要 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:动态规划 + 递归
状态转移方程:f(n) = f(n-1) + f(n-2)
java代码:
class Solution {
public int climbStairs1(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs1(n - 1) + climbStairs1(n - 2);
}
}
复杂度
- 时间复杂度:
O(n^n)
- 空间复杂度:
O(1)
复杂度呈指数增长,会超时。主要因为计算f(n)时,递归时,会又把前面的计算了一遍。
解法2:动态规划,hash缓存优化
在解法1的基础上,把前面计算过缓存下来即可。
java代码
class Solution {
Map<Integer, Integer> hash = new HashMap();
public int climbStairs2(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (hash.containsKey(n)) {
return hash.get(n);
} else {
int res = climbStairs2(n - 1) + climbStairs2(n - 2);
hash.put(n, res);
return res;
}
}
}
复杂度
- 时间复杂度:
O(n)
- 空间复杂度:
O(1)
解法3:循环代替动态规划
因为当前的解法f(n) = f(n-1) + f(n-2),所以当前的返回值只与前两个数相关,只要循环一次计算前两个值即可
class Solution {
public int climbStairs(int n) {
// 前面第2个值
int val1 = 0;
// 前面第1个值
int val2 = 0;
// 当前值
int res = 1;
for (int i = 0; i < n; i++) {
val1 = val2;
val2 = res;
res = val1 + val2;
}
return res;
}
}
复杂度
- 时间复杂度:
O(n)
- 空间复杂度:
O(1)