爬楼梯

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

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

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

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

1. 1 阶 + 1 阶
   2. 2 阶

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

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

思路分析：

根据题意，爬到第 n 层楼梯有两种方案：

先爬到 n - 1 层，再爬一层，分两步
先爬到 n - 2 层，再爬两层，分两步
记爬到第 n 的方案总数为 ways(n)，那么 ways(n) = ways(n - 1) 1 + ways(n - 2) 1。

这里 * 是分步计数乘法原理的应用，1 分别表示「再爬一层」和「再爬两层」这一种方案，+ 是分类计数加法原理的应用，两种方案都可以完成任务，总的方案数是二者之和。

大家可以自行在纸上画出这个问题的递归结构，很容易发现其实和我们在上一节画出的「斐波拉契数列」的递归结构是一样的。为此我们先采用「记忆化递归」，然后再使用「动态规划」求解。

方法一：记忆化递归

1. 自顶向下

   Java
   public class Solution {
   private int[] memo;
   public int climbStairs(int n) {
    memo = new int[n + 1];
    return dfs(n);
   }
   private int dfs(int n) {
    // 递归出口
    if (memo[n] != 0) return memo[n];
    if (n == 0 || n== 1) return 1;
    return memo[n] = dfs(n - 1) + dfs(n - 2);
   }
   }

   复杂度分析：
   时间复杂度：O(N)，这里 N 是输入的楼梯层数
   空间复杂度：O(N)

方法二：动态规划

第 1 步：状态定义

1. **dp[i]** 表示爬上第 i 层台阶的方法数

第 2 步：推导状态转移方程

1. 根据题意，爬到第 n 层楼梯有两种方案：
   1. 先爬到 n - 1 层，再爬一层，分两步
   2. 先爬到 n - 2 层，再爬两层，分两步
   3. **dp[i] = dp[i - 1] + dp[i - 2]**
2. 可以看出爬楼梯问题的「状态转移方程」就是「斐波拉契数列」的通项公式。

第 3 步：思考初始化

1. **dp[0] **无意义，它也不会被以后的计算过程参考到，因此可以不赋值或者任意赋值
2. **dp[1] = 1**、**dp[2] = 2 **这是显然的

第 4 步：思考输出

1. 显然，输出为 dp[n]

const climbStairs = function(n) {
  if(n < 2) return n;
  const dp = [0, 1];
  for(let i = 2; i <= n; i++) {
    // 两种方法爬到当前层
    // 先到i-1的位置，再爬一层
    // 或者先到i-2的位置，再爬两层
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};