采访者：改变！连一个动态规划模型的三个特点他都不懂

前言之前我们简单总结了动态规划的解题套路，很多人反馈受益匪浅（如果你是动态规划的初学者，那就是强烈建议看一看！）不过有读者说虽然了解了动态规划的解题套路，但是没有提到动态规划的一些主要特点，比如没有后遗症，所以今天就简单回顾一下解法动态规划的一个简单问题。问题例程及其主要特征。什么样的问题适合动态规划？我们在学习动态规划解题技巧一文中提到，只要问题满足“递归+重复”，基本就可以断定可以用动态规划来解决问题。简单的说，动态规划可以解决的问题符合一个“一个模型三个特点”的模型：多阶段决策最优解模型，多阶段就是可以把问题分解成多个阶段来求解，而每个阶段通常都有一个最优解，可以用每个阶段的最优解通过递推公式得到下一阶段的最优解，得到每个阶段的最优解。自然，全局最优解也就是求解三个特征的最优解。Substructure：上述模型中描述的每个阶段的最优解，即最优子结构没有后效：当前阶段的最优解只与上一阶段的最优解相关，不关心前一阶段。该阶段的最优解是如何得到的，后续阶段的决策（最优解）不会影响上一阶段问题的求解。重复的子问题：如果采用自上而下的方式解决问题，通常会出现重复的子问题，也就是我们所说的“递归+重复”。这时候，我们可以使用自下而上的套路来解决问题。如果你对上面的“一模三用”没有感觉也没关系，我们可以应用下面的动态规划解题模板来判断是否可以使用递归来求解。可能的话转步骤2分析递归过程中是否存在大量重复的子问题。使用备忘录保存子问题的解，避免大量重复计算（剪枝）改用自下而上的方法递归，即动态规划。接下来，我们先用上面的解题模板，通过一个比较有趣的练习来解题，然后再解释一下动态规划中“一个模型三个特征”问题的定义。下面这个8x8的格子，机器人需要从起始位置走到结束位置，而且每次只能往右或者往下走，粉红色的格子是障碍物，机器人无法通过，请教机器人如何很多时候是从开始位置到结束位置怎么移动？如果用动态规划来解这道题，可能一时半会看不出来，那我们就用穷举法看看怎么解吧。所谓穷举法就是计算出机器人所有的路径，然后将它们相加穷举法的使用方法，对于机器人的起始位置，它可以选择向下走或者向右走，所以数到终点的路径数是右边格子到终点的路径数与下面格子到终点的路径数之差并且，伪代码如下paths(start,end)=paths(gridbelowstart,end)+paths(gridontherightofstart,end)对于每一个格子，它也可以选择向左或向右走，因为它可以绘制对于每一个选择的格子，它符合如下递推公式：paths（机器人所在格子，终点）=paths（机器人所在格子下方格子，终点）+paths（机器人所在格子右边格子，终点）)表示为以下代码：privateintcountPaths(boolean[][]grid,introw,intcol){if(isObstacle(grid,row,col))return0;if(isAtEnd(grid,row,col))return1;returncountPaths(grid,row+1,col)+countPath(grid,row,col+1)}你能看到模式吗？这其实就是一个递归，那么如果使用递归会怎么样呢？以上图中的起点为例。如果你选择向右或向下，那么右边的下一个格子你也可以选择向右或向下。如果你选择在右边的格子里往下走，在下格子里往右走，这两条路径经过了同一个格子，两条路径相交了！也就是说，有一个重复的问题！每次机器人都可以选择向右走或者向下走，如果我们把它抽象成一个二叉树，结构如下：注：蓝色代表同一个正方形。既然是二叉树，时间复杂度显然是O(2^n)，指数级！原因当然是解中有大量重复的子问题（图中蓝色代表同一个方块，即重复的子问题），为了减少重复的子问题，我们需要使用备忘录保存中间结果（即分支缩减），可以大大降低时间复杂度。经过下面的“递归+备忘录”，时间复杂度和动态规划相差无几。但是，我们一直强调，尽量不要用递归来解决问题，因为递归层次太深的话，很容易造成栈溢出，那我们就用动态规划看看怎么解决吧。递归使用自上而下的方法来解决问题。对应这道题，它是从起点出发，推演到终点的所有路径，而动态规划是自下而上的，即从终点推演到起点。所有路径和.对于最右边和最下面的格子，由于它们只能往下或者往右走，所以它们的位置都用1标记，表示从这些格子中只有一条路径，如下图：最右边和最右边的路径数底部网格已填充，其他网格简单。显然，对于其他格子，paths(grid,end)=paths(下面的格子，end)+paths(右边的格子，end)注：如果格子是障碍物，到终点的路径数是0，表示每个格子到终点的路径总和等于其右边格子到终点的路径数与其下格子到终点的路径数之和观点。向左，从下到上，按照上面的递归公式依次填入每个格子中的路径数，如下，从起点到终点的路径总和显然是10+17=27。什么是时间复杂度？从下到上，从右到左，两层循环显然是O(n^2)，比原来递归的O(2^n)有了很大的提升。知道了解题思路，用代码实现问题不大。我们用一个二维数组grid[row][column]来表示图中的网格。如果格子是障碍物，它的元素值初始化为-1，其他格子元素初始化为0，所以我们只需要做两层循环就可以得到最终的解。代码如下，注释很详细。publicclassSolution相信大家应该都能看懂了{/***初始化网格，-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}};staticprivateintsumOfPaths(){//网格为8x8intN=8;/***初始化最右边的网格*/for(intj=0;j=0;i--){for(intj=N-2;j>=0;j--){//说明是障碍，不用计算if(GRIDS[i][j]==-1){continue;}/***求和每个格子到终点的路径数等于其右侧格子到终点的路径数与其下方格子到终点的路径数之和*如果右侧格子或下面是障碍物，到终点的路径数设置为0*/intrightPath=GRIDS[i+1][j]==-1?0:GRIDS[i+1][j];intbottomPath=GRIDS[i][j+1]==-1?0:GRIDS[i][j+1];GRIDS[i][j]=rightPath+bottomPath;}}/***遍历后起点网格对应的值就是最终的解*/returnGRIDS[0][0];}publicstaticvoidmain(String[]args){intresult=Solution.sumOfPaths();System.out.println("result="+result);}}可以看出使用自下而上的动态规划求解的整体思路还是比较清晰的高效。现在，我们回过头来看一下如何理解动态规划的一个模型和三个特点：即多阶段决策的最优解模型。首先，让我们看一下多阶段的起始位置到终点。第一阶段可以看做是从起点往右走或者往下走。第一阶段选好格子后，第二阶段就是从第一阶段选择的格子往右或往下走。..，可以看出它的问题解确实是由多阶段最优组成的。三个特征1.最优子结构上面我们说过，对于每个网格，到终点的路径数是右边网格到终点的路径数和下面网格到终点的路径数之和端点paths(grid,end)=paths(下面的网格,end)+paths(右边的网格,end)的意思是对于每一个网格，只要计算它的最优子结构（从网格上的路径数）右到终点加上从下面的格子到终点的路径数）），那么这个格子到终点的路径之和就是最优解，然后可以看出GRID[0]上面计算的[0]也是全局最优解。2.无后遗症。每个格子到终点的路径数只与它右边的格子到终点的路径数和它下面的格子到终点的路径数有关。它并不关心两者之间的路径数是如何得到的，即当前阶段的解只与上一阶段的解有关，并不关心这些解是如何计算出来的。同时，当前阶段的求解完成后，不会影响上一阶段的求解。那就是没有后遗症的意思。3、如果重复子问题用递归的方式来做，我们之前分析过，显然存在重复子问题。综上所述，这道题符合动态规划的“一个模型的三个特征”，所以可以用动态规划来解题总结本文用一个比较常见的习题来帮助大家复习动态规划的特点：一个模型结合三个特点，相信大家应该对这些概念有了更深的理解。其实忘记这些概念，使用上面介绍的动态规划的四个步骤基本可以解决大部分动态规划问题，但是理解这些概念可以进一步加深我们的理解。对于动态规划的理想，知其所以然也很重要。本文转载自微信公众号“码海”，可通过以下二维码关注。转载本文请联系码海公众号。