爬楼梯-70

[sl1673495]

假设你正在爬楼梯。需要 n  阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题的思路是，对于到达任意一个阶梯 n，都可以分为「从前两个台阶跨两步到达」和「从前一个台阶跨一步到达」，而本题的目的是取「方式之和」，所以动态规划的状态转移方程是
dp[n] = dp[n - 1] + dp[n - 2]

1. 从上一阶的位置跨一步，取 dp[i - 1]的到达方式数量。
2. 从上两阶的位置跨两步，取 dp[i - 2]的到达方式数量。

然后把这两个方式的数量相加，就是到达第 n 阶的方式总数。

题解

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  let dp = [];

  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    // 到达第 n 阶的方式
    // 1. 从上一阶的位置跨一步 取dp[i - 1]的到达方式数量
    // 2. 从上两阶的位置跨两步 取dp[i - 2]的到达方式数量
    // 把两种方式数量相加 即可得到到达第n阶方式数量
    dp[i] = dp[i - 2] + dp[i - 1];
  }

  return dp[n];
};