爬楼梯

描述： 假设你正在爬楼梯，需要 n 步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例： 比如 n=3，1+1+1=1+2=2+1=3，共有 3 种不同的方法 返回 3

思路分析

• 通过以下列举的分析，可推出规律是： 除了 1 阶楼梯和 2 阶楼梯是一种和两种方法之外，第 n 阶的楼梯的方法是第 i-1 阶楼梯和第 i-2 阶楼梯所用方法的和

0 =0 0种方法

1 = 1 种方法

2 = 1+1 =2 2种方法

3=1+1+1=1+2=2+1 3种方法

4 = 1*4 = 1+2+1 = 1+1+2 = 2+1+1 = 2+2 5种方法

5 = 1*5 = 2+1+2 =2+2+1 = 1+2+2 =1+2+1+1 = 1+1+2+1 = 2+1+1+1 = 1+1+1+2 8种方法

代码实现

1、数组方式

js

const climbStairs = function(n) {
  let dp = [0, 1, 2]; // 初始数组 前面三个没有规律
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 从3开始都是可以由前面两个元素相加推导出来
  }
  return dp[n];
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));

2、递归方式

js

const climbStairs = function(n) {
  function item(n) {
    // 循环退出条件
    if (n === 1) return 1;
    if (n === 2) return 2;
    return item(n - 1) + item(n - 2); // 将递归到1个楼梯和两个楼梯 最后反推到n个楼梯
  }
  return item(n);
};
console.log(climbStairs(3), climbStairs(4), climbStairs(5));