https://leetcode-cn.com/problems/climbing-stairs/
参考答案 – 递归
时间复杂度为 O(2^n)，会超时。
class Solution:
def climbStairs(self, n: int) -> int:
if n < 3: return n
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
参考答案 – 递归加缓存
时间复杂度为 O(n)。
class Solution:
def climbStairs(self, n: int) -> int:
return self.recursion(n, {})
def recursion(self, n, m):
if n < 3:
return n
if n in m:
return m[n]
m[n] = self.recursion(n - 1, m) + self.recursion(n - 2, m)
return m[n]
参考答案 – 递推
时间复杂度为 O(n)。
Python 代码
class Solution:
def climbStairs(self, n: int) -> int:
if n < 3:
return n
f1, f2 = 1, 2
for i in range(2, n):
f1, f2 = f2, f1 + f2
return f2
JavaScript 代码
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n < 3) {
return n;
}
let f1 = 1;
let f2 = 2;
for (let i = 3; i <= n; i += 1) {
[f1, f2] = [f2, f1 + f2];
}
return f2;
};
Rust 代码
impl Solution {
pub fn climb_stairs(n: i32) -> i32 {
if n < 3 {
return n;
}
let mut f1 = 1;
let mut f2 = 2;
for _ in 2..n {
let next = f1 + f2;
f1 = f2;
f2 = next;
}
return f2;
}
}
Golang 代码
func climbStairs(n int) int {
if n < 3 {
return n
}
f1, f2 := 1, 2
for i := 3; i <= n; i++ {
f1, f2 = f2, f1+f2
}
return f2
}
C++ 代码
class Solution {
public:
int climbStairs(int n) {
if (n < 3) {
return n;
}
int f1 = 1;
int f2 = 2;
for (int i = 2; i < n; i++) {
int next = f1 + f2;
f1 = f2;
f2 = next;
}
return f2;
}
};
