LeetCode 70.爬楼梯(简单)

题目描述

假设你正在爬楼梯。需要 ​​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)