JavaScript 爬楼梯算法问题
🌙
手机阅读
本文目录结构
爬楼梯问题
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法？
递归方法分析
由分析可知，假设我们只差最后一步就能走上第10级阶梯，这个时候一共有两种情况，因为每一步只允许走1级或2级阶梯， 因此分别为从8级阶梯和从9九级阶梯走上去的情况。因此从0到10级阶梯的走法数量就等于从0到9级阶梯的走法数量加上 从0到8级阶梯的走法数量。依次类推，我们可以得到一个递归关系，递归结束的标志为从0到1级阶梯的走法数量和从0到 2级阶梯的走法数量。
代码实现
function getClimbingWays(n) {
if (n < 1) {
return 0;
}
if (n === 1) {
return 1;
}
if (n === 2) {
return 2;
}
return getClimbingWays(n - 1) + getClimbingWays(n - 2);
}
使用这种方法时整个的递归过程是一个二叉树的结构，因此该方法的时间复杂度可以近似的看为 O(2^n)，空间复杂度 为递归的深度 O(logn)。
备忘录方法
分析递归的方法我们可以发现，其实有很多的计算过程其实是重复的，因此我们可以使用一个数组，将已经计算出的值给 保存下来，每次计算时，先判断计算结果是否已经存在，如果已经存在就直接使用。
代码实现
let map = new Map();
function getClimbingWays(n) {
if (n < 1) {
return 0;
}
if (n === 1) {
return 1;
}
if (n === 2) {
return 2;
}
if (map.has(n)) {
return map.get(n);
} else {
let value = getClimbingWays(n - 1) + getClimbingWays(n - 2);
map.set(n, value);
return value;
}
}
通过这种方式，我们将算法的时间复杂度降低为 O(n)，但是增加空间复杂度为 O(n)
迭代法
通过观察，我们可以发现每一个值其实都等于它的前面两个值的和，因此我们可以使用自底向上的方式来实现。
代码实现
function getClimbingWays(n) {
if (n < 1) {
return 0;
}
if (n === 1) {
return 1;
}
if (n === 2) {
return 2;
}
let a = 1,
b = 2,
temp = 0;
for (let i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
通过这种方式我们可以将算法的时间复杂度降低为 O(n)，并且将算法的空间复杂度降低为 O(1)。
详细资料可以参考： 《漫画：什么是动态规划？（整合版）》
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
