共计 2508 个字符，预计需要花费 7 分钟才能阅读完成。
从本题中咱们能够学到蕴含重复子问题，能够采纳记忆化的形式，复用计算后的值；并用动静布局的思维，找到动静转移方程，采纳循环实现。
题目形容：
题目：假如咱们须要爬一个楼梯，这个楼梯一共有 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)。
后有采纳了动静布局的形式，失去转移方程式，采纳循环的形式实现。
如果对你有帮忙，请关注【前端技能解锁】：
