前言大厂面试中经常出现动态规划算法题。是很适合考考生的一类题型，因为难度适中，需要一定的技巧，而且根据练习的不同可能会有一定的变化，所以如果想去大厂的话，建议大家复习一下诸如此类的问题，接下来我会写一些动态规划相关问题的解答，希望能帮助大家理解这类习题。帮助。今天我们来看一道腾讯面试题。题目如下：有一个8×8的格子如下。机器人需要从入口走到出口。每次只能向右或向下。粉色格子是障碍物，机器人无法通过。机器人从入口走到出口最少需要多少步？问题分析这道题其实和我们上篇文章分析过的题差不多，只是问的是从入口到出口最多有多少条路，而这道题稍微改了一下找到所需的最少步骤数。总体思路其实是一样的。大家可以先看看之前的文章，想一想，再看我的解决方案。首先想到的当然是暴力破解。对于机器人来说，每一步都可以往下走，也可以往右走，所以我们可以用蛮力算法求出所有路径需要的步数，然后求出最少的步数。伪代码如下paths(start,end)=1+min(paths(start下面的格子,end),paths(start,end右边的格子))的时间复杂度是多少？对于机器人所在的每一个格子，下一步可以走两步（向右或向下），一共N个格子，所以总共要走O(2^n)步，指数级！蛮力解决显然有一个大问题。这道题其实是用动态规划的思想来考察解法的。动态规划的主要解题思路是用自下而上的思维来解题。求入口到出口的最短路径叫自上而上，求出口到入口的最短路径叫自底向上。怎么问，我们先看看之前的出口位置。对于这个位置，它到出口只需要一步，所以我们把它的位置填1。同理，它之前的位置必须通过这个位置到出口，所以它的最后一个位置要填2，以此类推，我们可以填写右边的这些格子，然后走几步到出口。同理，我们可以得到底部格子到出口的位置，如下：有人可能会说，如果右边和底部的格子里有障碍物怎么办？做，如下这种情况下，由于障碍物上方的格子不能通向出口，所以障碍物上方的格子应该用无穷大填充（另外，显然，所有障碍物本身所在的格子也应该用无穷大填充），如上图最右边一栏底部格子填满的数字，就是动态规划的basecase。计算完basecase后，必须得到动态规划的“状态转移方程”。得到状态转移方程后，动态规划求解就基本搞定了。让我们一起看看如何解决它。现在我们从右到左，从下到上遍历每个格子，求出每个格子到出口的最小步数。我们知道每个格子下一步只能往右或往下走，所以每个格子到出口的最少步数可以根据下面的公式求解。当前格子到出口的最小步数=1+min（右格子到出口的最小步数，下格子到出口的最小步数）。这个公式就是状态转移方程。例如，以下面的两个网格A和B为例。对于网格A，它的右边网格，从下面的网格到出口的最小步数是1，所以到出口的最小步数是1+min(1,1)=2。对于B，最小步数它右边的格子到出口的步数是3，它下面的格子是障碍物，到出口的步数是无限的，所以B到出口的最小步数是1+min(∞,3)=4.以此类推，我们可以得到每个格子到出口的最小步数，如下图：填充后，到达入口位置。显然，从入口到出口的最小步数应该是1+min(13,13)=14step。下面是代码，注释写的很清楚，相信大家应该都能看懂。publicclassSolution{/***初始化网格，假设是8x8，-1表示网格是障碍物*/privatestaticfinalintGRIDS[][]={{0,0,0,0,0,0,0,0},{0,0,-1,0,0,0,-1,0},{0,0,0,0,-1,0,0,0},{-1,0,-1,0,0,-1,0,0},{0,0,-1,0,0,0,0,0},{0,0,0,-1,-1,0,-1,0},{0,-1,0,0,0,-1,0,0},{0,0,0,0,0,0,0,0}};staticprivateintgetMinStep(){/***gridis8x8*/intN=8;//如果格子是障碍物，则将这个格子到出口的距离标记为无穷大（这里表示为100000），也就是说这个格子无法通行到出口。integerinfinity=100000;/***初始化最右边的格子，从最后一列的倒数第二行开始（因为最后一个格子是出口）*/for(introw=N-2;row>=0;row--){//如果当前格子的下一格子不是障碍物，则当前格子到出口的最小步数为1+下一格子到出口的步数if(GRIDS[row+1][N-1]!=-1){GRIDS[row][N-1]=1+GRIDS[row+1][N-1];}else{//如果下一个格子是障碍物，则这个格子到出口的步数设置为无穷大（代表道路不通），这里使用最大正整数值表示GRIDS[row][N-1]=infinity;}}/***初始化最下面的格子，从最后一行的倒数第二列开始（因为最后一个格子是出口）*/for(intcolumn=N-2;column>=0;column--){//如果当前格子右边的格子不是障碍物，当前格子到出口的最小步数是1+右边格子的步数到出口if(GRIDS[N-1][column+1]!=-1){GRIDS[N-1][column]=1+GRIDS[N-1][column+1];}else{//如果是障碍物，走到出口步数无限大，这里用正整数的最大值表示GRIDS[N-1][列]=infinity;}}/***从右到左，从下到上填充每个格子，因为最右边和最下面的格子都初始化好了，*所以从倒数第二行倒数第二列开始遍历*/for(inti=N-2;i>=0;i--){for(intj=N-2;j>=0;j--){//表示是障碍物，距离的步数到出口的格子显然是无穷大的（表示路被堵住了）if(GRIDS[i][j]==-1){GRIDS[i][j]=infinity;continue;}/***最小当前格子到出口的步数为1+(右边格子到出口的步数与下一格子到出口的步数之和的最小值)*/GRIDS[i][j]=1+Math.min(GRIDS[i+1][j],GRIDS[i][j+1]);}}/***遍历后，起始网格对应的值为最终solution*/returnGRIDS[0][0];}publicstaticvoidmain(String[]args){intresult=Solution.getMinStep();System.out.println("result="+result);}}理清思路后，剩下的代码实现比较简单。接下来我们分析一下时间复杂度和空间复杂度time复杂度中间有两层循环，所以显然是O(N^2)。至于空间复杂度，我们没有分配额外的空间来存储数据，而是复用了表示迷宫的网格数组GRIDS，所以空间复杂度为O(1)。有人会问，为什么可以直接用GRIDS计算从格子到出口的步数，这样就把格子的信息（比如是否是障碍物）都覆盖了。这里需要了解一下动态规划的无后效，什么是无后效。以上面的例子为例，对于图中的网格A和B，当前网格到状态转移方程出口的最小步数=1+min（右边网格到当前网格的最小步数exit,下格子到出口的最小步数Steps)我们可以看到计算到出口的最短步数只和它的右格子和下格子到出口的最小步数有关(steps此时右格子和下格子的步数已经计算出来了）也就是说，对于A来说，对于格子B来说，它只关心它的右格子和下格子的步数。至于这两个格子的步数是怎么计算的，他们不管，这叫无后效。因此，我们可以从右到左，从下到上遍历每个格子的步数，填充到GRIDS中，这样虽然覆盖了GRIDS中的格子信息，但是不需要从中计算步数遍历的网格到出口。步数没有影响。巧妙的使用noaftereffect可以在很多场景下有效的压缩空间，降低空间复杂度。本文转载自微信公众号“码海”，可通过以下二维码关注。转载本文请联系码海公众号。
