题目地址(70. 爬楼梯)
https://leetcode.cn/problems/climbing-stairs/
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
前置知识
- 递归和动态规划
公司
- 暂无
思路
- 动态规则就是要找出状态转移方程
关键点
- f(n) = f(n-1) + f(n-2)，n = 1，f(n)=1；n=2时，f(n)=2
代码
- 语言支持：Java
Java Code:
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int a = 1;
int b = 2;
for (int i = 3; i <= n; ++i) {
int tmp = a;
a = b;
b = tmp + b;
}
return b;
}
}
另一种常见写法
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int current = 0;
int a = 1;
int b = 2;
for (int i = 3; i <= n; ++i) {
current = a + b;
a = b;
b = current;
}
return current;
}
Go Code:
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
a, b, current := 1, 2, 0
// go没有前置的++i
for i := 3; i <= n; i++ {
current = a + b
a = b
b = current
}
return current
}
复杂度分析
令 n 为数组长度。
- 时间复杂度：
- 空间复杂度：
