题目描述：假设你正在爬楼梯。需要 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 阶

思路：
这道题目有两个关键的特征：

  1. 要求你给出达成某个目的的解法个数
  2. 不要求你给出每一种解法对应的具体路径

递归解法：

  1. /**
  2. * @param {number} n
  3. * @return {number}
  4. */
  5. const climbStairs = function(n) {
  6.     // 处理递归边界
  7.     if(n === 1) {
  8.         return 1
  9.     }
  10.     if(n === 2){
  11.         return 2
  12.     }
  13.     // 递归计算
  14.     return climbStairs(n-1) + climbStairs(n-2)
  15. };

这个解法问题比较大，丢进 OJ 会直接超时。

记忆搜索法

重复计算带来了时间效率上的问题，要想解决这类问题，最直接的思路就是用空间换时间，也就是想办法记住之前已经求解过的结果。这里我们只需要定义一个数组：

  1. const f = []

每计算出一个 f(n) 的值，都把它塞进 f 数组里。下次要用到这个值的时候，直接取出来就行了：

  1. /**
  2. * @param {number} n
  3. * @return {number}
  4. */
  5. // 定义记忆数组 f
  6. const f = []
  7. const climbStairs = function(n) {
  8.   if(n==1) {
  9.       return 1
  10.   }
  11.   if(n==2) {
  12.       return 2
  13.   }
  14.   // 若f[n]不存在，则进行计算
  15.   if(f[n]===undefined)  f[n] = climbStairs(n-1) + climbStairs(n-2)
  16.   // 若f[n]已经求解过，直接返回
  17.   return f[n]
  18. };

动态规划

  1. /**
  2. * @param {number} n
  3. * @return {number}
  4. */
  5. const climbStairs = function(n) {
  6.     // 初始化状态数组
  7.     const f = [];
  8.     // 初始化已知值
  9.     f[1] = 1;
  10.     f[2] = 2;
  11.     // 动态更新每一层楼梯对应的结果
  12.     for(let i = 3;i <= n;i++){
  13.         f[i] = f[i-2] + f[i-1];
  14.     }
  15.     // 返回目标值
  16.     return f[n];
  17. };
  1. 递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
  2. 结合记忆化搜索，明确状态转移方程
  3. 递归代码转化为迭代表达（这一步不一定是必要的，1、2本身为思维路径，而并非代码实现。若你成长为熟手，2中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。