前端跳槽面试算法——动态规划

摘要：我记得大三参加腾讯的校招面试时只准备了几种常见的排序算法就足以应对了，然而今年包括今日头条在内的多家大厂的前端笔试题目中都出现了贪心算法动态规划分治算法等进阶性的算法题目。

本篇博客参考今日头条银国徽老师的《js版数据结构与算法》
Part1改编自《漫画算法》原作者：程序员小灰

前言

众所周知，与后台开发人员相比，算法是我们前端开发人员的一个弱项。

而近两年随着互联网行业竞争愈发激烈，市场上对前端岗位的算法要求也有一定的提升。

我记得大三参加腾讯的校招面试时只准备了几种常见的排序算法就足以应对了，然而今年包括今日头条在内的多家大厂的前端笔试题目中都出现了"贪心算法""动态规划""分治算法"等进阶性的算法题目。如果在没有提前准备的情况下现场应对这类进阶性的算法题目并没有那么简单。

如果你这些算法都没有听过却又想进大厂的话，别犹豫了，趁着头发没掉光赶紧学吧！

本篇博客将分为两个部分

Part1：通过漫画形象地讲述动态规划的思想

Part2：配合一道有关动态规划的LeetCode真题进行实战演练

Part1：漫画理解 

一一一一一一一一一一一一一一一一一一一一一一一一一

题目：

有一个只能容纳10本书的单层书架，你每次只能放1本或2本书。要求用程序求出你将书架填满一共有多少种方法。

比如，每次放1本书，一共放10次，这是其中一种方法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

再比如，每次放2本书，一共放5次，这是另一种方法。我们可以简写成 2,2,2,2,2。

当然，除此之外，还有很多很多种方式。

一一一一一一一一一一一一一一一一一一一一一一一一一

第一种:

第二种:

这里为了方便大家理解，我再另外举一个例子：

如图所示 假设只能通过road1或road2这两条路径到达终点

(相当于我们把放书的最后一步分为放2本和放1本两种情况)

到达road1有x条路经(相当于0到8本的放法数量F(8))

到达road2有y条路经(相当于0到9本的放法数量F(9))

那么到达终点的可能性就是 x+y了 (也就是我们前面推导的 F(10) = F(9)+F(8) )

       F(1) = 1;

       F(2) = 2;

       F(n) = F(n-1)+F(n-2)（n>=3）

相信大家看完一定对动态规划有了一个初步的认识，

这里大家可以自己先尝试写一下这道题的代码

接下来我们先来通过一道LeetCode实战原题加深我们对动态规划的理解

Part2：实战演练

不同路径Ⅱ

LeetCode第63题  原题地址

题目难度 中等

题目描述

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？


 网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m和n的值均不超过 100。

实例1

输入:
 [ 
   [0,0,0], 
   [0,1,0],
   [0,0,0] 
] 
输出: 2 
解释:
3x3 网格的正中间有一个障碍物。
 从左上角到右下角一共有 2 条不同的路径： 
1. 向右 -> 向右 -> 向下 -> 向下 
2. 向下 -> 向下 -> 向右 -> 向右

题目解析

相信大家已经看出来了，我们这道题与我们漫画中演示的题目几乎一致。

但它又提升了一点难度，我们需要考虑到障碍物的情况。

还记得我们之前提到的动态规划三要素【最优子结构】【边界】和【状态转移公式】吗？

拿题目中给出的图片进行举例：

在不考虑障碍物的情况下，我们利用动态规划的思想，到达终点有几种情况呢？

很明显是两种:  从终点上方或终点左方到达

                                                              7 * 3 矩阵

那我们很容易得出这个7*3的矩阵的终点 F(7*3) 的最优子结构为 F(6*3) 和 F(7*2）

至此它的状态转移公式也一目了然: F(m*n) = F(m-1*n) + F(m*n-1)

最后我们考虑一下它的边界情况:

经过评论区同学的指正，其实我们之前考虑的F(2*2)边界情况继续往下分也可以分为一列和一行即F(1*2) + F(2*1)两种情况。

所有的F(m*n)的矩阵最后都可以拆分为一行和一列的情况，所以我们这里边界情况只有两种。

第一种边界F(1*n) 即1行n列

第二种边界F(n*1) 即n行1列

代码实现

export default (arr) => {
  let dp = (m, n) => {
    // 检查起始或者目标元素是不是1(障碍物)，如果起始或者最后那个格就是1，说明怎么都怎么不到那，
    // 直接返回0
    if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
      return 0
    }
    // 有边界
    if (m < 2 || n < 2) {
      // 第一种边界 1行n列
      if (m < 2) {
        return arr[m - 1].includes(1) ? 0 : 1
      } else {
        // 第二种边界 n行1列
        for (let i = 0; i < m; i++) {
          if (arr[i][0] === 1) {
            return 0
          }
        }
        return 1
      }
    } else {
      // 递归
      return dp(m - 1, n) + dp(m, n - 1)
    }
  }
  return dp(arr.length, arr[0].length)
}

补充：时间复杂度分析

问题分析

感谢同学们在评论区提出的问题

首先说明我们上方代码是没有问题的，但是在LeetCode上的第27个测试用例上超出了时间限制

这个测试用例相对复杂，是一个33*22的二维矩阵

那为什么矩阵到达一定长度时我们的方法时间复杂度会过高呢?

我们先回顾一下我们之前的思路:

F(10) = F(9) + F(8)             

F(9) = F(8) + F(7)      

将F(9)分解后那么F(10) 可以写成

 F(8) + F(8) + F(7)

而F(8) 又= F(7) + F(6)

那么继续将F(8)分解 F(10) 可以写成 

F(7) + F(7) +F(7) + F(6) + F(6)

注意到了吗?

越向下划分重复的就越多，可能你会觉得不就是多加一次F(n)的值吗

但是这里我必须要提醒你的是：

F(n)不单纯是一个值的引用，他是一个递归函数，我们每重复一次它都会重新执行一次F函数

我们不讨论时间复杂度具体怎样计算

但这里我可以告诉大家我们之前的方法时间复杂度是O(2^n)

那么怎样改进呢?

提出思路

在这里提出两个思路，大家也可以尝试自己写一下：

缓存每一次计算出的值，也就是记录下F(9),F(8),F(7)...的值，每次递归到有之前计算过数据直接拿值，而不用再次重复调用递归函数。

从下向上(由起点至终点)计算，由于每次只依赖前两个数据，通过两个变量只保存前两次的数据就可以了，如计算F(3)只依赖F(1)和F(2)，计算F(6)只依赖F(5)和F(4)。

代码优化

// 传入二维数组
arr => {
    // 行数
    let n = arr.length;
    if(!n){
        return 0;
    }
    // 列数
    let m = arr[0].length;
    // 起点或终点为障碍物
    if(arr[0][0] === 1 || arr[n - 1][m - 1] === 1){
        return 0;
    }
    // 记录到达每个位置的路径可能数
    var rode= [];
    // 遍历每一行
    for(let i = 0; i < n; i++){
        rode[i] = [];    // 遍历每一行的每个元素
        for(let j = 0; j < m; j++){
            // 若某节点是障碍物，则通向该节点的路径数量为0
            if(arr[i][j] === 1){
                rode[i][j] = 0;
            } else if(i === 0){
                // 若是第一行 每个节点是否能通过都依赖它左方节点
                rode[i][j] = rode[i][j - 1] === 0 ? 0 : 1;
            } else if(j === 0){
                // 若是第一列 每个节点是否能通过都依赖它上方节点                
                rode[i][j] = rode[i - 1][j] === 0 ? 0 : 1;
            } else {
                // 否则递归
                rode[i][j] = rode[i - 1][j] + rode[i][j - 1];
            }
        }
    }
    return rode[n - 1][m - 1];
}

参考

程序员小灰—— 漫画：什么是动态规划？

今日头条银国徽老师——js版数据结构与算法

大家也可以参考FE_Yuan同学针对这篇博客做的补充：前端面试算法-动态规划

总结

大家发现了吗，当你掌握了动态规划的三要素【最优子结构】【边界】和【状态转移公式】

后，解决动态规划的算法题目并不是很难。但是其中的思想是需要我们好好消化吸收的。

相信以后遇到这类问题你也可以迎刃而解。