假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
解题思路
用动态规划，爬到第 n 阶楼梯的方法众数 = 到第 n - 1 阶和第 n - 2 阶的种数之和
f(n) = f(n - 1) + f(n - 2)
初始值：第一阶楼梯只有一种，第二阶楼梯有两种(1+1或2)
如果采用动态规划数组, 则要额外O(n)的空间
优化方式是滚动数组，因为计算当前值只跟前两个值有关，所以每次保留前两个值就行
空间复杂度为O(1)
代码
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n; // f(0) = 0, f(1) = 1, f(2) = 2
}
int a = 1; // n = 1
int b = 2; // n = 2
int c = 0;
for (int i = 3; i <= n; i++) {
c = a + b; // 加上前两个数
a = b; // 保留前一个的前一个数
b = c; // 保留前一个数
}
return c;
}
}
