从本题中咱们能够学到蕴含重复子问题，能够采纳记忆化的形式，复用计算后的值；并用动静布局的思维，找到动静转移方程，采纳循环实现。
题目形容：
题目：假如咱们须要爬一个楼梯，这个楼梯一共有 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)); // 5console.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)); // 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在动静布局中有一个 动静转移方程 的概念，实际上就是形容问题构造的数学模式：
**
听起来很浅近，实际上能够把 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总结：
以上是对这道题的解析发现，能够应用斐波那契额的思路，采纳递归的形式实现，工夫复杂度在 O(2^n)，成指数级回升；
又从中看出有重叠子问题，采取记忆化递归，将反复计算的值缓存起来，免得屡次计算，工夫复杂度降到了 O(n)。
后有采纳了动静布局的形式，失去转移方程式，采纳循环的形式实现。
如果对你有帮忙，请关注【前端技能解锁】：