题目描述
假设你正在爬楼梯。需要 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
题目分析
这道题还是一道经典的斐波那契数列题。我们可以维护一个 dp
数组,dp[i]
表示走到第 i
阶的方法数。每次可以走一步或者两步,所以走到第 i
阶的方法数就是从第 i-1
阶的方法数加上第 i-2
阶的方法数,至此我们就确定了状态转移方程 dp[i] = dp[i-1] + dp[i-2]
。同样因为当前状态 i 只与前两个状态有关,所以我们只需维护两个变量存储这两个状态,就能使空间复杂度降至
题解
执行用时: 0 ms
内存消耗: 38.3 MB
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2, cur = 0;
for (int i = 2; i < n; ++i) {
cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return cur;
}
}
题目来源:力扣(LeetCode)
发表评论