#70.爬楼梯

LeetCode 原题链接

#实现思路

• 这道题的核心是找到一个规律：爬到第 n 阶楼梯的方法数等于爬到第 n-1 阶和第 n-2 阶的方法数之和。因为最后一步可以是爬 1 阶或者 2 阶，所以总方法数就是前两阶方法数的和。
• 这就是一个典型的斐波那契数列问题，可以使用动态规划来解决。
• 定义一个数组 dp，其中 dp[i] 表示爬到第 i 阶楼梯的方法数。初始条件是 dp[1] = 1 和 dp[2] = 2。
• 从第 3 阶开始，使用循环计算 dp[i] = dp[i - 1] + dp[i - 2]，直到计算到 dp[n]。

#代码实现

var climbStairs = function (n) {
  if (n === 1) return 1;
  if (n === 2) return 2;
  const dp = [1, 2];

  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n - 1];
};