【Leetcode 每日一题 - 扩展】70. 爬楼梯
问题背景
假设你正在爬楼梯。需要
n
n
n 阶你才能到达楼顶。
每次你可以爬
1
1
1 或
2
2
2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
数据约束
- 1 ≤ n ≤ 45 1 \le n \le 45 1≤n≤45
解题过程
经典动态规划入门题，实际上结果符合斐波那契数列，状态转移只与个别变量有关，甚至可以不用定义数组进行记忆化搜索。
具体实现
class Solution {
public int climbStairs(int n) {
int pre, cur, next;
pre = cur = 1;
for (int i = 0; i < n; i++) {
next = pre + cur;
pre = cur;
cur = next;
}
return pre;
}
}