【博客大赛】面试官在“逗”你系列：到底应该怎么爬楼梯？！

江南才子

直奔主题

　　算法题是在面试过程中考察候选人逻辑思维能力、手写代码能力的一种方式，因为有一句古话说的好：“说一千道一万，不如写段代码看一看”。


　　今天我们就来个单刀直入，直奔主题，从一个真实面试题

到底怎么爬楼梯

来聊一聊算法中的

动态规划

。

面试真题

小明家有一楼梯共有10级台阶，每次可以爬1级或2级，问小明爬到第10级台阶，一共有多少种走法？

　　为什么是“小明”呢？这是个奇怪的问题~

真题分析

　　很多同学在第一次遇到这个爬楼梯的问题可能会比较

懵

,不知道该如何来解决。我们首先需要做的就是寻找这个问题的关键点：

每次只能爬1级或2级

。

递归思想

　　小明每次只能爬1级或2级，那么对于爬到第10级台阶来说，最后一次操作为走1级（此时处于第9级台阶上）或走2级（此时处于第8级台阶上）。
假定我们有个表达式f可以来计算到达某阶台阶的走法，那么对于第10阶来说，这个表达式就应该为：

f(10) = f(9) + f(8)

。

　　对于这个表达式，是不是有种瞬间回到那初、高中的年代~

　　按如上规则，再次考虑，爬到第9级台阶时，最后一次操作为走1级（此时处于第8级台阶上）或走2级（此时处于第7级台阶上），此处的表达式为：

f(9) = f(8) + f(7)

。
　　......
　　依次处理，当爬到第3级台阶时，计算的表达式就是

f(3) = f(2) + f(1)

。
　　那爬到第2级台阶有几种方式呢：每次走1级或者一次走2级，也就是一共有2种走法，

f(2) = 2

。
　　爬到第1级台阶的方式肯定只有一种：走1级，

f(1) = 1

。
　　按我们的思考逻辑，相关代码如下：

/**
 * @method climbStairs
 * @description 爬楼梯
 * @param {number} n 楼梯台阶数
 * @return {number} 一共有多少种走法
*/
function climbStairs (n) {
  if (n === 1) { return 1 };
  if (n === 2) { return 2 };
  let num = 0;
  num = climbStairs(n - 1) + climbStairs(n - 2);
  return num;
}
// 调用函数，输出结果
let num = climbStairs(10);
console.log(num); // 89

　　Congratulations~我们已经完成啦，得到了正确的结果。

　　就在你满脸微笑、志得意满的向面试官讲解思路的时候，面试官十有八九会一副老狐狸得逞的样子，继续问你，假如n的值比较大的，如40之类的，上面定义的

的执行性能如何。
　　我们来看下执行的性能：
　　测试代码如下：
console.time();
let num = climbStairs(40);
console.log(num);
console.timeEnd()

　　我的mac配置如下：

MacBook Pro 
处理器：2.5 GHz 四核Intel Core i7
内存： 16GB

　　连续执行三次数据如下：
　　|序号|结果|执行时间|
　　|----|----|----|
　　|1| 165580141 | 811.077ms |
　　|2| 165580141 | 817.025ms |
　　|3| 165580141 | 814.803ms |

　　注：在执行过程中有卡顿，不是瞬间输出~，如果执行的是

(100)

，你应该会瞬间听到风扇启动的呜呜声~

递归思想优化

　　在上面代码

climbStairs

的基础上我们来进行优化处理。我们仔细分析代码的执行流程，就会发现有很多重复计算的地方，比如说

(5)

就会在

(6-1)

、

(7-2)

时被重复计算，这就浪费了时间和性能。
　　那我们就选择使用空间换时间的策略，设置对象

，保存爬到某级台阶的结果，避免重复计算，

对象的结果如下：

let numbers = {
  1: 1,
  2: 2
}

　　优化后代码如下：

/**
 * @method climbStairs
 * @description 爬楼梯
 * @param {number} n 楼梯台阶数
 * @return {number} 一共有多少种走法
*/
function climbStairs (n) {
  // 存储计算的结果，key(台阶) : num(走法)
  let numbers = {
  1: 1,
  2: 2
  };
  let tmpClimbStairs = function (n) {
  // 已存在的数据，直接返回，不再重新计算
  if (numbers[n]) {
    return numbers[n];
  }
  // 不存在的数据，进行计算
  let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2);
  // 计算完成后，存放如numbers中，下次可以直接使用
  numbers[n] = num;
  // 返回结果
  return num;
  }
  // 计算结果
  let num = tmpClimbStairs(n);
  // 返回结果
  return num;
}

　　相同环境下，我们再来执行测试，连续执行三次数据如下：
　　|序号|结果|执行时间|
　　|----|----|----|
　　|1| 165580141 | 7.100ms |
　　|2| 165580141 | 7.478ms |
　　|3| 165580141 | 6.260ms |

　　消耗的时间竟然相差百倍之多，It's amazing！说明我们使用空间换时间的策略是正确的。

　　执行结果几乎是瞬间输出的，执行如丝袜奶茶般顺滑~此时此刻你可以再次执行

climbStairs(100)

来体验下绝对的性能飙升！
　　这道面试题处理成这样已经是非常OK的了，但是如果你已经感到彻底满足，为自己的聪明才智感到骄傲了，你就会听到面试官可爱（恨）的声音传来：”还有别的方法或性能更好的方法来实现吗？“
　　是不是心中一口老血想喷出来~面试官是不是故意的，是不是在针对我~
　　哈哈，不慌不慌，小场面~

递归与递推

　　递归与递推是两种不同的看待、分析问题的思路。

递归

：自顶向下的处理逻辑，有相应的临界点（终止递归的点）；

递推

：自底向上的处理逻辑，到达目标点结束。
递推思想

　　我们重新使用

递推

的方式再来看这个问题。

• 爬到第1级台阶，有1种方式。

  (1) = 1

  ；
  
• 爬到第2级台阶，有2种方式：每次1级或1次2级。

  (2) = 2

  ；
  
• 爬到第3级台阶的情况呢？
  

　　不要忘了我们之前分析的关键点：每次只能1级或2级，
　　对于第3级台阶来说，可以是从第1级台阶出发也可以是从第2级台阶出发，
所以

(3) = f(2) + f(1)

• 同理可得爬到第4级台阶的情况，

  (4) = f(3) + f(2)

　　我们得出一个结论：对于第N(N > 2)级台阶，其表达式为

(N) = f(N-1) + f(N-2)

。那么我们在结算的过程中，每次都记录下

(N-1)

和

(N-2)

的值，逐级迁移这个值，就可以得到

(N)

了。
　　现在

代码如下：
/**
 * @method climbStairs
 * @description 爬楼梯
 * @param {number} n 楼梯台阶数
 * @return {number} 一共有多少种走法
*/
function climbStair (n) {
  // 通过观察，我们可只第1级和第2级都是返回对应的n
  if (n <= 2) {
  return n;
  } else {
  // 对于n > 2的情况
  let i = 1;  // 初始存放第1级台阶的走法，对应的是f(N-2)
  let j = 2;  // 初始存放第2级台阶的走法，对应的是f(N-1);
  // 定义走法num
  let num;
  // 从第3级开始，执行循环操作
  for (let k = 3; k <= n; k++) {
    // f(N) = f(N-1) + f(N-2)
    num = i + j;
    // 同时移动
    // 将f(N-1)的值给f(N-2)
    i = j;
    // 将当前值给f(N-1)
    j = num;
  }
  // 返回结果
  return num;
  }
}

　　这一次我们直接在时间复杂度上降低了，变成了

(N)

,执行起来更加是和那啥一样，流畅、顺滑~

　　我们来看下测试效果，连续执行三次测试结果如下：
　　|序号|结果|执行时间|
　　|----|----|----|
　　|1| 165580141 | 6.570ms |
　　|2| 165580141 | 6.647ms |
　　|3| 165580141 | 6.658ms |

　　相对于

递归

的实现方式，

递推

的实现从时间复杂度上更低，执行也会更高效~

　　此时此刻，这个爬楼梯的问题终于是回答圆满了，这个时候面试官看你就会像

丈母娘看女婿一样，怎么看怎么可爱

。
　　动态规划的算法问题有很多种不同的形式，爬楼梯是其中的一种。在这里胡哥要给大家留一道面试题啦，看看大家对动态规划是不是有了深刻的理解。
　　面试真题如下：
你是一个有信仰的强盗，有一排房屋等待你去抢劫，在抢劫中不能相邻的房屋不能抢，只能间隔一个或多个房屋进行抢劫，房屋中钱财都是非负整数，数据格式如下：

[3, 4, 5, 2, 1, 1]

，请计算出你能抢到的最大金额是多少。

　　这个强盗相当有信仰，竟然不都抢走~

欢迎各位小伙伴留言，谈谈你对动态规划的理解，留下这道面试题的答案，一起来探讨交流~
后记

　　以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得

点赞

、

收藏

呀，关注胡哥有话说，学习前端不迷路，欢迎多多留言交流...
> 胡哥有话说，专注于大前端技术领域，分享前端系统架构，框架实现原理，最新最高效的技术实践！