@wy 2020-12-22T11:29:28.000000Z 字数 2444 阅读 427

【LeetCode】70. 爬楼梯

算法

【LeetCode】70. 爬楼梯

题目：假设我们需要爬一个楼梯，这个楼梯一共有 N 阶，可以一步跨越 1 个或者 2 个台阶，那么爬完楼梯一共有多少种方式?

示例：

输入：2
输出：2

有2种方式可以爬楼梯，跳1+1阶，跳2阶

示例：

输入：3
输出：3

有3种方法爬楼梯，跳1+1+1阶，1+2阶，2+1阶；

推理：

1阶楼梯，跳1阶，有1种方法；
2阶楼梯，跳1+1阶，跳2阶，有2种方法；
3阶楼梯，跳1+1+1阶，1+2阶，2+1阶，有3种方法；
4阶楼梯，跳1+1+1+1阶，1+2+1阶，1+1+2阶，2+1+1阶，2+2阶，有5中方法；

如果要跳 n 阶台阶，最后一步动作可以是上1阶，也可以上2阶，可以转化为：

如果选择最后上 1 阶到达，则求出上 n - 1 个台阶有多少种方法
如果选择最后上 2 阶到达，则求出上 n - 2 个台阶有多少种方法

以上4阶楼梯举例，选择最后上 1 阶到达，则为 1 + (1+1+1)阶，1 + (2+1)阶，1 + (1+2)阶，括号中的方法，正好是上 3 阶楼梯的方法；选择最后上 2 阶到达，则为 2 + (1+1)阶，2 + (2)阶，括号中的方法，正好是上 2 阶楼梯的方法。

所以最后上 n 阶楼梯可以得出：

fn(n) = fn(n - 1) + fn(n - 2)

类似是斐波那契数列的形式了，可以用递归进行实现。

递归实现代码：

var climbStairs = function(n) {
  if(n === 1) return 1
  if(n === 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
};
console.log(climbStairs(4));  // 5
console.log(climbStairs(20));  // 10946

可以画个图具象表示：

递归算法的时间复杂度怎么计算？用子问题个数乘以解决一个子问题需要的时间。

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)

然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，随着 n 越大，复杂度会越来越高。

在以上递归过程中，会有很多重复的计算。例如计算上 5 阶梯的方法，则需要计算上 4 阶梯的方法，和上 3 阶梯的方法；要计算上 4 阶梯的方法，则需要计算上 3 阶梯的方法，和上 2 阶梯的方法。

计算上 3 阶梯的方法在第一次计算后，之后又要重新计算，这样会造成重复计算。

这是一个典型的重叠子问题，怎么让重复计算的结果更高效的利用呢？

可以采用记忆化递归的方式，把已经计算好的结果缓存起来，以备遇到已经计算过的数字，可以直接使用，不再耗时计算。

记忆化递归

记忆化递归代码实现：

const climbStairs = function(n) {
  const cache = {}  // 缓存计算过的值
  const loop = (n) => {
    if(n === 1) return 1
    if(n === 2) return 2
    if(!cache[n]){
      cache[n] = loop(n - 1) + loop(n - 2)
    }
    return cache[n]
  }
  return loop(n)
};
console.log(climbStairs(4));  // 5
console.log(climbStairs(20));  // 10946

从上面看出，定义对象来存储已计算好的结果，key 值为上的阶梯数，value 值为阶梯计算后的方法数，每个阶梯只需要计算一次，可以达到 O(n) 的时间复杂度。

这种方法是 自顶向下 计算，从一个规模较大的原问题 fn(20) 开始，一步步拆分为越来越小的规模计算，直到最后不能拆分为止的 fn(1)，fn(2) 为止，然后逐层返回结果。

还有一种方式是 自底向上 计算，先从问题最小规模的 fn(1)，fn(2) 开始，不断的扩大规模，直到推导出最终原问题 fn(20) 的值，便得到最终的结果。

自底向上 属于动态规划的思路，可以使用循环完成。

动态规划

动态规划代码：


const climbStairs = function(n) {
  const result = []
  result[0] = 0;  // 0 阶 占位
  result[1] = 1;
  result[2] = 2;
  for(let i = 3; i <= n; i++){
    result[i] =  result[i - 1] + result[i - 2]
  }
  return result[n]
};
console.log(climbStairs(4));  // 5
console.log(climbStairs(20));  // 10946

在动态规划中有一个 动态转移方程 的概念，实际上就是描述问题结构的数学形式：

听起来很高深，实际上可以把 fn(n) 当做一个状态，这个状态是由状态 fn(n-1) 和 fn(n-2) 相加转移而来的，通过不断的循环，转态不断的转移到要求值的 n 上，仅此而已。

上面的代码还可以进一步简化，当前的状态只和两个状态相关，记录两个状态便能够得到另一个状态，在循环过程中记录两个状态即可。

简化代码：

const climbStairs = function(n) {
  if(n < 1) return 0
  if(n === 1 ) return 1
  if(n === 2 ) return 2
  let current = 2; // 前一个
  let prev = 1; // 前前一个
  let  sum = 0;
  for(let i = 3; i <= n; i++){
    sum = current + prev
    prev = current
    current = sum
  }
  return current
};
console.log(climbStairs(4));  // 5
console.log(climbStairs(20));  // 10946

总结：

以上是对这道题的解析发现，可以使用斐波那契额的思路，采用递归的方式实现，时间复杂度在 O(2^n)，成指数级上升；

又从中看出有重叠子问题，可以将重复计算的值缓存起来，以免多次计算，时间复杂度降到了 O(n)。

后有采用了动态规划的方式，得到转移方程式，采用循环的方式实现。

【LeetCode】70. 爬楼梯