转：
【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)。
后有采用了动态规划的方式，得到转移方程式，采用循环的方式实现。
如果对你有帮助，请关注【前端技能解锁】：
转：