跳到主要内容

70.爬楼梯

链接：70.爬楼梯
难度：Easy
标签：记忆化搜索、数学、动态规划
简介：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题解 1 - typescript​

  • 编辑时间：2020-06-13
  • 执行用时：84ms
  • 内存消耗：32.3MB
  • 编程语言：typescript
  • 解法介绍：dp[i]=dp[i-1]+dp[i-2]。
function climbStairs(n: number): number {
  const dp = [1, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

题解 2 - typescript​

  • 编辑时间：2021-09-03
  • 执行用时：68ms
  • 内存消耗：39.4MB
  • 编程语言：typescript
  • 解法介绍：动态规划。
function climbStairs(n: number): number {
  const dp = new Array(n + 1);
  dp[0] = dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

题解 3 - cpp​

  • 编辑时间：2021-12-21
  • 内存消耗：6.1MB
  • 编程语言：cpp
  • 解法介绍：动态规划。
class Solution {
   public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

题解 4 - python​

  • 编辑时间：2023-12-10
  • 执行用时：36ms
  • 内存消耗：16.67MB
  • 编程语言：python
  • 解法介绍：dp。
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        print(dp)
        return dp[n]