class Solution {
public:
int climbStairs(int n) {
}
};
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原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-12-10 14:09:09
func climbStairs(n int) int {
sqrt5 := math.Sqrt(5)
pow1 := math.Pow((1+sqrt5)/2, float64(n+1))
pow2 := math.Pow((1-sqrt5)/2, float64(n+1))
return int(math.Round((pow1 - pow2) / sqrt5))
}
javascript 解法, 执行用时: 60 ms, 内存消耗: 40.9 MB, 提交时间: 2023-12-10 14:08:35
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for (let i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-11-28 10:03:04
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1, sum;
for(int i = 0; i < n - 1; i++){
sum = a + b;
a = b;
b = sum;
}
return b;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.5 MB, 提交时间: 2023-11-28 10:01:48
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++ ) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-07-18 10:22:45
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2021-07-23 10:14:48
func climbStairs(n int) int {
f := make([]int, n+4)
f[0] = 0
f[1] = 1
f[2] = 2
for i := 3; i < n+4; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2021-07-17 12:09:13
func climbStairs(n int) int {
f := make([]int, n+3)
f[0] = 0
f[1] = 1
f[2] = 2
for i := 3; i <= n+2; i++ {
f[i] = f[i-1] + f[i-2]
}
return f[n]
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2019-07-12 10:25:58
func climbStairs(n int) int {
if n < 3 {
return n
}
n1 := 1
n2 := 2
for i:=3; i<=n; i++ {
n1, n2 = n2, n1+n2
}
return n2
}