【JS】【LeetCode】70. 爬楼梯

Z时代
2024-01-10
分类：技术分享

从本题中我们可以学到包含重复子问题，可以采用记忆化的方式，复用计算后的值；并用动态规划的思想，找到动态转移方程，采用循环实现。

题目描述：

题目：假设我们需要爬一个楼梯，这个楼梯一共有 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 阶楼梯可以得出：

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

递归实现代码：

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));  // 5console.log(climbStairs(20));  // 10946

可以画个图具象表示：

【JS】【LeetCode】70. 爬楼梯

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

首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 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));  // 5console.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));  // 5console.log(climbStairs(20));  // 10946

在动态规划中有一个 动态转移方程 的概念，实际上就是描述问题结构的数学形式：
**
【JS】【LeetCode】70. 爬楼梯

听起来很高深，实际上可以把 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));  // 5console.log(climbStairs(20));  // 10946