爬楼梯

题目描述

你正在爬楼梯。它有 n 阶台阶，每次你可以爬 1 阶或 2 阶。你有多少种不同的方法可以爬到楼梯的顶部？

解题步骤

为了计算爬楼梯的不同方法数，我们可以使用动态规划的思想来解决问题。

1. 定义状态：我们可以将问题转化为每个台阶的不同方法数。令 dp[i] 表示爬到第 i 个台阶的不同方法数。

2. 初始状态：根据题目的约束，当台阶数为 1 时，只有一种方法；当台阶数为 2 时，有两种方法。即 dp[1] = 1，dp[2] = 2。

3. 状态转移方程：对于第 i 个台阶，我们可以从第 i-1 个台阶爬一阶上来，或者从第 i-2 个台阶直接跨两阶上来。因此，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。

4. 最终解：问题的解即为爬到最后一个台阶的不同方法数，即 dp[n]，其中 n 是台阶的总数。

下面是使用动态规划解决爬楼梯问题的算法框架：

function climbStairs(n) {
  if (n === 1) {
    return 1;
  }

  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;

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

  return dp[n];
}