解题步骤

  1. 定义子问题：f(n) = f(n - 1) + f(n - 2)
  2. 反复执行：从 2 循环到 n ，执行上述公式

通过动态规划的方式实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (n)

    1. function climbStairs(n) {
    2.   if (n < 2) return 1;
    4.   const dp = [1, 1];
    6.   for (let i = 2; i <= n; i++) {
    7.       dp[i] = dp[i - 1] + dp[i - 2];
    8.   }
    10.   return dp[n];
    11. }

代码中存在一个循环，所以时间复杂度是 O (n)。而空间复杂度也是 O (n)，因为使用了数组存储数据，数据会随着 n 增大而增大。

通过动态规划的方式实现（优化后）

  • 时间复杂度：O (n)

  • 空间复杂度：O (1)

    1. function climbStairs(n) {
    2.   if (n < 2) return 1;
    4.   let dp0 = 1;
    5.   let dp1 = 1;
    7.   for (let i = 2; i <= n; i++) {
    8.       const temp = dp0;
    9.       dp0 = dp1;
    10.       dp1 = dp1 + temp;
    11.   }
    13.   return dp1;
    14. }

代码中存在一个循环，所以时间复杂度是 O (n)。而空间复杂度是 O (1)，因为把数据存储的方式改成了单个变量的存储方式。