直奔主题
算法题是在面试过程中考察候选人逻辑思维能力, 手写代码能力的一种方式, 因为有一句古话说的好:"说一千道一万, 不如写段代码看一看".
今天我们就来个单刀直入, 直奔主题, 从一个真实面试题到底怎么爬楼梯来聊一聊算法中的动态规划 .
面试真题
小明家有一楼梯共有 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 之类的, 上面定义的 climbStairs 的执行性能如何.
我们来看下执行的性能:
测试代码如下:
- 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 |
注: 在执行过程中有卡顿, 不是瞬间输出~, 如果执行的是 climbStairs(100), 你应该会瞬间听到风扇启动的呜呜声~
递归思想优化
在上面代码 climbStairs 的基础上我们来进行优化处理. 我们仔细分析代码的执行流程, 就会发现有很多重复计算的地方, 比如说 f(5)就会在 f(6-1),f(7-2)时被重复计算, 这就浪费了时间和性能.
那我们就选择使用空间换时间的策略, 设置对象 numbers, 保存爬到某级台阶的结果, 避免重复计算, numbers 对象的结果如下:
- 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 种方式. f(1) = 1;
爬到第 2 级台阶, 有 2 种方式: 每次 1 级或 1 次 2 级. f(2) = 2;
爬到第 3 级台阶的情况呢?
不要忘了我们之前分析的关键点: 每次只能 1 级或 2 级,
对于第 3 级台阶来说, 可以是从第 1 级台阶出发也可以是从第 2 级台阶出发,
所以 f(3) = f(2) + f(1)
同理可得爬到第 4 级台阶的情况, f(4) = f(3) + f(2)
我们得出一个结论: 对于第 N(N> 2)级台阶, 其表达式为 f(N) = f(N-1) + f(N-2). 那么我们在结算的过程中, 每次都记录下 f(N-1)和 f(N-2)的值, 逐级迁移这个值, 就可以得到 f(N)了.
现在 climbStairs 代码如下:
- /**
- * @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;
- }
- }
这一次我们直接在时间复杂度上降低了, 变成了 O(N), 执行起来更加是和那啥一样, 流畅, 顺滑~
我们来看下测试效果,连续执行三次测试结果如下: | 序号 | 结果 | 执行时间 |
---|---|---|---|
1 | 165580141 | 6.570ms | |
2 | 165580141 | 6.647ms | |
3 | 165580141 | 6.658ms |
相对于递归的实现方式, 递推的实现从时间复杂度上更低, 执行也会更高效~
此时此刻, 这个爬楼梯的问题终于是回答圆满了, 这个时候面试官看你就会像丈母娘看女婿一样, 怎么看怎么可爱.
动态规划的算法问题有很多种不同的形式, 爬楼梯是其中的一种. 在这里胡哥要给大家留一道面试题啦, 看看大家对动态规划是不是有了深刻的理解.
面试真题如下:
你是一个有信仰的强盗, 有一排房屋等待你去抢劫, 在抢劫中不能相邻的房屋不能抢, 只能间隔一个或多个房屋进行抢劫, 房屋中钱财都是非负整数, 数据格式如下:[3, 4, 5, 2, 1, 1], 请计算出你能抢到的最大金额是多少.
这个强盗相当有信仰, 竟然不都抢走~
欢迎各位小伙伴留言, 谈谈你对动态规划的理解, 留下这道面试题的答案, 一起来探讨交流~
后记
来源: http://blog.51cto.com/13482114/2740075