在上一篇文章中，我们详细讲了递归。如果大家仔细敲下相关代码，那是不可能什么都得不到的。同时，敏锐的小伙伴可能已经发现了，接下来要讲的内容——动态规划，没错，终于讲到动态规划了。说到动态规划，不知道大家的第一反应是什么，难不难？看不懂别人的帖子？这些都不是事，按照我的步骤一步步来，等写完几篇再总结一下。到时候面对动态规划就不再难了。以下正文：（本文篇幅还是比较长，请耐心等待）1.什么是暴力递归说白了：暴力递归就是尝试1.将问题转化为同类问题的子问题withreducedscale2.继续递归（basecase）有明确的不必要条件3.得到子问题结果后有决策过程4.不记录每个子问题的解2.什么是动态规划？调用过程保存下来，下次遇到相同的过程直接调用即可（空间换时间）。也就是说，当遇到重复调用的递归过程时，可以使用动态规划进行优化。以众所周知的斐波那契数列为例。斐波那契数列规定第一项为1，第二项为1，后面的每一项F(n)=F(n-1)+F(n-2)。我们解决第7项的过程是这样的：我们把第7项的值展开后，会发现整个递归过程会有很多重复的过程。这时候，我们可以使用动态规划来优化解决方案。F(5)我们解完一次后，保存它的值，下次需要找F(5)的时候直接取就可以了，减少了重复求解的过程。同样，对于每一个求解的所有值都这样做，这就是动态规划。上面概念性的东西太抽象了，好吧，我们来看两个实际的话题，仔细感受一下从暴力递归到动态规划的魅力。三、机器人运动问题1、题目描述对于N个格子（从1到N个标签），机器人初始处在Start（1<=Start<=N）位置，需要走过K（K>=1）步骤。（一次一格），来到目标位置（1<=aim<=N），问机器人有多少种运动方式？（注意：两端的格子只能往中间走，在中间的任意格子里，可以选择往左走或往右走）2.思路1从尝试开始/***1.从尝试开始**@作者Java和算法学习：Monday*/publicstaticintway1(intn,intstart,intaim,intk){if(n<2||start<1||start>n||aim<1||aim>n||k<1){返回-1;}returnprocess1(start,k,aim,n);}/***计算机器人满足条件的方式有多少**@paramcurrent当前位置*@paramremaining剩余步数*@paramaim目标位置*@paramnGridnumber*/privatestaticintprocess1(intcurrent,intremaining,intaim,intn){//basecase,不需要走if(remaining==0){//当剩余步数为0，当前处于瞄准位置，所以这是一种行走方式returncurrent==aim?1:0;}//还有步要走if(current==1){//最左边只能往右走returnprocess1(2,remaining-1,aim,n);}elseif(current==n){//在最右边，只能往左走returnprocess1(n-1,remaining-1,aim,n);}else{//在中间的位置，可以向左走也可以向右走，所以是两种情况的结果之和returnprocess1(current-1,remaining-1,aim,n)+process1(current+1,剩余-1,目标,n);}}上面的代码是按照题目要求写的最符合自然智慧的代码，也是最容易理解的代码。在递归调用过程中，目标位置和格子数始终不变，只有当前位置和剩余步数一直在变化。对于第6格剩余步数为8的某情况，分析调用过程如下：会发现有重复的调用过程，所以这个可以通过动态规划来优化。如果没有重复调用的过程，动态规划无法优化，也无法优化。定义一个缓存表的二维数组dp。机器人当前位置范围为1\~n，剩余步数范围为0\~k。dp表(n+1)*(k+1)一定能把所有的情况都包含进来。一开始dp表都是-1。后面递归调用时，先判断缓存表中是否有值。如果有(!=-1)，直接返回值，没有值就走递归过程。同时，在每次递归返回结果之前，必须更新缓存表dp。/***2.愚蠢的缓存方法**@authorJava与算法学习：周一*/publicstaticintway2(intn,intstart,intaim,intk){if(n<2||start<1||开始>n||目标<1||目标>n||k<1){return-1;}//机器人当前位置范围为1~n，剩余步数范围为0~k，dp表(n+1)*(k+1)必须能覆盖所有情况int[][]dp=newint[n+1][k+1];对于(inti=0;i<=n;i++){for(intj=0;j<=k;j++){dp[i][j]=-1;}}}//dp[current][remaining]==-1,表示未统计//dp[current][remaining]!=-1,表示已计算，结果保存returnprocess2(start,k,aim,n,dp);}/***计算机器人满足条件的运动有多少种，傻傻的缓存方法**@paramcurrent当前位置*@paramremaining剩余步数*@paramaimtargetposition*@paramngridnumber*/privatestaticintprocess2(intcurrent,intremaining,intaim,intn,int[][]dp){//缓存表已经有值，直接返回if(dp[当前][剩余]!=-1){返回dp[当前][剩余];}//NonebeforeCalculatedintanswer;如果（剩余==0）{答案=当前==目标？1:0;}elseif(current==1){answer=process2(2,remaining-1,aim,n,dp);}elseif(current==n){answer=process2(n-1,remaining-1,aim,n,dp);}else{answer=process2(current-1,remaining-1,aim,n,dp)+process2(current+1,remaining-n,p,aim,);}//在返回之前更新缓存dp[current][remaining]=answer;returndp[current][remaining];}因为这个方法中的递归调用过程是自上而下的，所以这个方法也是从上调用的向下动态规划的同时，如果dp表中有数据，则会直接返回，类似于记忆，所以也叫记忆搜索。愚蠢的缓存方式在暴力递归过程中加入了一个dp数组来存储之前生成的结果，因此优化了重复调用的过程。但是结束了吗？当然不是。4.最终版动态规划我们在第二种方法中绘制dp表。假设格子数n=5，start=2，aim=4，步数k=6。从第一种方法的递归过程分析如何填写dp表(1)因为格子的个数为n=5，所以当前位置的范围是1\~5，第0行没有用到，这以“×”表示；因为步数k=6，剩余步数范围为0\~6；publicstaticintway1(intn,intstart,intaim,intk){if(n<2||start<1||start>n||aim<1||aim>n||k<1){返回-1；}returnprocess1(start,k,aim,n);}main函数调用递归函数时，求start=2,k=6的值，即(2,6)的值，初始表即可得到如下(2)当剩余步数为0时，aim=4时当前位置为1，其余为0；//basecase，不需要行走if(remaining==0){//当剩余步数为0时，当前处于目标位置，所以这是一种行走方式returncurrent==aim?1:0;}当当前位置为1时，只能走到第二个格子，同时一个格子的剩余步数减1（即取决于左下方网格的值）；当当前位置为n=5时，只能走到n-1=4格（即取决于左上角的值）；对于任意一个非边缘位置，可以走到n-1和n+1个单元格（也就是靠左下左上的值）。dp表可以这样得到：（3）据此，我们可以按照从上到下，从左到右的顺序来填写整个表。如下图，(2,6)的最终值为13，即最终的结果为13。（4）根据上面的分析，动态规划代码可以这样写：/***3.动态规划最终版**@authorJava与算法学习：Monday*/publicstaticintway3(intn,intstart,intaim,intk){if(n<2||start<1||start>n||aim<1||aim>n||k<1){return-1;}//机器人当前位置范围为1~n，剩余步数范围为0~k，dp表(n+1)*(k+1)必须能包含所有情况int[][]dp=新整数[n+1][k+1];//当剩余步数为0时，当前位置为1dp[aim][0]=1;for(intremaining=1;remaining<=k;remaining++){//第一行，取决于左下角的值dp[1][remaining]=dp[2][remaining-1];//第一行和第n行分别计算后，这里就不用判断越界问题了for(intcurrent=2;current<=n-1;current++){//非边行，取决于左下角和左上角的值dp[current][remaining]=dp[current-1][remaining-1]+dp[current+1][remaining-1];}}//第n行，取决于左上角的值dp[n][remaining]=dp[n-1][remaining-1];}returndp[start][k];}看完整个过程，是不是豁然开朗，如果直接给你最后的代码，那肯定看不懂。同时，不建议死记硬背这张动态规划表。动态规划表只是结果，不是原因。我们从最初的尝试开始，一步一步推导。这就是状态转换的过程。如果想直接一步写出最终的动态规划代码，需要不断的实践和总结。看到这里，相信大家都有所收获。所有代码：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/dynamicprogramming/RobotWalk.java趁热打铁，又一个问题。四、卡片问题1、题目描述给定一个正整数数组arr，将代表不同数值的卡片排成一行。玩家A和玩家B轮流拿每张牌（可以看到所有的牌），规定玩家A先拿，玩家B后拿。但每位玩家一次只能拿走最左边或最右边的牌。选手A和选手B都非常聪明，请返回最后获胜者的分数。2.思路1从尝试开始(1)分析先手的情况，定义一个函数f(arr,L,R)，代表先手在数组arr[L...R].L和R是下标。1）如果L==R，表示现在只剩下一张牌，直接返回arr[L]；2）否则，表示还剩多张牌，两种情况取L位置，score=arr[L]+g[arr,L+1,R]（函数g是生成的最大分数反手）走R位，score=arr[R]+g[arr,L,R-1]因为我是先围棋，所以最后得分是以上两者中的最大值。（二）分析秒手情况1）如果L==R，说明现在只剩下一张牌，此时我是秒手，先选剩下的一张。无奈只好返回0；2)否则，表示还剩一张以上的牌。如果两种情况先取L位，我的二手分数=f[arr,L+1,R]，即我取[L+1,R]；如果我先取R位置，我的第二个分数=f[arr,L,R-1]，也就是我取第一个状态下[L,R-1]最好的分数。因为我是第二位选手，大家都非常聪明，所以第一位选手肯定只会留给我更少的分数，所以最后的分数是以上两位中最低的。(3)代码/***1.从尝试开始**@authorJava和算法学习：星期一*/publicstaticintwin1(int[]arr){if(arr==null||arr.length==0){返回0;}intbefore=f1(arr,0,arr.length-1);intafter=g1(arr,0,arr.length-1);返回Math.max（之前，之后）；}/***第一手状态获得的最大分数*/privatestaticintf1(int[]arr,intL,intR){if(L==R){returnarr[L];}//多于一张左牌intp1=arr[L]+g1(arr,L+1,R);intp2=arr[R]+g1(arr,L,R-1);返回Math.max(p1,p2);}/***第二玩家状态下获得的最大分数*/privatestaticintg1(int[]arr,intL,intR){if(L==R){return0;}//对手占据L位置Thenumberintp1=f1(arr,L+1,R);//占据R位置的对手数量intp2=f1(arr,L,R-1);returnMath.min(p1,p2);}3.思路2.傻缓存方式优化首先分析是否存在重复调用过程，然后可以使用动态规划进行优化。L和R的值是不断变化的，f函数又依赖于g函数，g函数又依赖于f函数，所以我们不妨设计两张表。/***2.愚蠢的缓存方法**@authorJava和算法学习：周一*/publicstaticintwin2(int[]arr){if(arr==null||arr.length==0){return0;}intN=arr.length;int[][]fMap=newint[N][N];int[][]gMap=newint[N][N];for(inti=0;i
