本文转载请联系Java极客技术公众号。大家好，我是阿凡，动态规划（DynamicProgramming），简称DP，相信大家在日常工作或者学习的过程中都遇到过这个词，而动态规划也是面试过程中最喜欢问的问题，阿芬在她经历的几次采访中都被问到。真是惨，好在阿芬学会了一些简单的套路。先从一个很多人应该都熟悉的话题说起。案例1问题：一只青蛙一次最多可以跳1步或2步。青蛙跳到n步有多少种跳法？刚开始思考这个话题的时候可能没什么想法，但是我们可以稍微想一想。假设一只青蛙要跳上n级台阶，总共有f(n)种跳跃方法。那么当n=0,f(0)=0时，就没有了，当然也没有办法跳步了。n=1,f(1)=1;当只有一步时，只能跳一次；n=2,f(2)=2,当有两步的时候，可以有两种跳法，一种跳和两种跳，如果我们是三步的话，是不是可以只把一步和两步相加？所以我们可以想到f(3)=f(2)+f(1)，所以我们可以推导出f(n)=f(n-1)+f(n-2)；上面的编码分析可以想象，那么我们就需要用代码来实现了，对于需要用到前面的记录，我们可以考虑用一维数组来记录，所以就有了下面的代码。publicintdp(intn){if(n<=0){return0;}int[]dp=newint[n+1];dp[0]=0;dp[1]=1;dp[2]=2;//之所以从3开始是因为2不满足下面的规则for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}解释一下上面的代码，首先我们创建一个一维数组dp来记录每一步的跳转，然后从下标三开始遍历，使用公式f(n)=f(n-1)+f(n-2);进行赋值，结果可以直接输出dp[n]对应的值。通过以上案例的分析，我们来思考一下对于动态规划问题我们需要做些什么。我们先定义了n步有f(n)种跳跃方式，然后计算了f(0)、f(1)、f(2)，然后找到了f(n)=f(n-1)+f(n-2);按照这种思路，我们可以总结出三个步骤，分别是定义变量：定义已知需要求解的变量，比如上面的n和f(n)；求表达式：求f(n)andf(n-1)andf(n-2)，还有其他的表达式，比如上面的f(n)=f(n-1)+f(n-2)，这一步往往是最困难的；求初值：一定要求出所有的临界条件，比如上面的f(0)=0,f(1)=1,f(2)=2；以上步骤是一般步骤，往往在第一步中我们将集合f(n)设置为一个数组，根据具体场景可以是一维数组也可以是二维数组。在上面的例子中，我们定义了一个一维数组，通常我们需要求解什么数组就定义什么。我们再这样看一下LeetCode的原题案例2：一个机器人位于一个mxn的格子的左上角（起点在下图中标记为“Start”）。机器人一次只能向下或向右移动一步。机器人尝试到达网格的右下角（下图中标记为“完成”）。总共有多少条不同的路径？img我们按照上面三个步骤依次解决。既然是一个mxn的网格，很明显我们需要用一个二维数组来求解，所以我们定义d[m][n]表示移动到右下角需要的总步数mxn网格；由于机器人只能向右下方移动，下一个格子只能从左侧或上方到达，所以到达mxn的步数等于(m-1)xn+mx(n-1)，也就是说，d[m][n]=d[m-1][n]+d[m][n-1]；定义初值d[0][n]=1，d[n][0]=1，即当只有一行或一列时，只有一种方法，全部向下或向右移动;encodingpublicintdp(intm,intn){if(m<=0||n<=0){return0;}int[][]dp=newint[m][n];//只有一列时for(inti=0;i
