动态规划步骤

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。主要可以分为3个步骤：

第一步骤：定义数组元素的含义

我们会用一个数组来保存历史s数据，假设用一维数组 dp[] 。
这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么含义

第二步骤：找出数组元素之间的关系式

类似于归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的。
也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]。

第三步骤：找出初始值

类似于归纳法的，比如当我们要计算 dp[n] 时，要利用 dp[n-1]，dp[n-2].....dp[1]。
我们假设dp[n] = dp[n-1] + dp[n-2]，一直推下去的话，会有 dp[3] = dp[2] + dp[1]。
到这里，dp[2] 和 dp[1] 不能再分解了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值。

有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么。

案例

案例1：一维数组形式

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

第一步骤：定义数组元素的含义

求什么问题，就定义什么含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法。所以定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。

第二步骤：找出数组元素之间的关系式

我们可以从目标出发，去找关系，怎么找，是最核心最难的一个，dp[n] 究竟会等于什么呢？对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式从第 n-1 级跳上来
从第 n-2 级跳上来我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]

第三步骤：找出初始值

由于递推关系中的分别有n， n-1，n-2，最小值为n-2
由于我们问题的最小是求dp[1]，所以令最小值n-2为1，则n-1为2，n为3，所以初始值为dp[1]，dp[2]显然，dp[1] = 1，dp[2]=2

代码：

int f( int n ){// 先创建一个数组来保存历史数据int[] dp = new int[n+1];// 给出初始值dp[1] = 1;dp[2] = 2;// 通过关系式来计算出 dp[n]for(int i = 3; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}// 把最终结果返回return dp[n];
}

案例2：二维数组形式

问题描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

第一步骤：定义数组元素的含义

求什么问题，就定义什么含义，我们的问题是要求机器人从(0,0)到达（3，7）坐标总共有多少种路径。所以定义 dp[i] [j] 的含义为：机器人从(0,0)到达（i，j）坐标总共有dp[i] [j]种路径。

第二步骤：找出数组元素之间的关系式

我们可以从目标出发，去找关系，怎么找，是最核心最难的一个，dp[i] [j]究竟会等于什么呢？对于这道题，由于机器人可以向下走或者向右走，所以有两种方式到达从 (i-1, j) 这个位置走一步到达
从 (i, j-1) 这个位置走一步到达我们是要算所有可能的路径，所以有dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

第三步骤：找出初始值

由于递推关系中的分别有（i，j）， （i-1，j），（i，j-1），两个都取最小值时有（i-1，j-1）
由于我们的问题最小是求dp[0][0],令最小值（i-1，j-1）为（0，0）时，有i=1，j=1。
所以初始值为dp[1][0]，dp[0][1]，但除了递推公式的初值，我们知道递推公式只能推出dp[m][n],其中m>=1,n>=1
所以dp[m][0]，dp[0][n],dp[0][0]并不能由递推公式求出，所以特殊处理显然，dp[1][0] = 1，dp[0][1]=1，dp[0][0]=0,dp[m][0]=1,dp[0][n]=1,

代码：

int uniquePaths(int i, int j){int[][] dp = new int[i+1][j+1]; // // 初始化for(int m = 1; m <= i; m++)  dp[m][0] = 1;for(int n = 1; n <= j; n++)  dp[0][n] = 1;dp[0][0]=0;dp[1][0]=1;dp[0][1]=1;// 通过关系式来计算出 dp[i][j]for (int m = 1; m <= i; m++) {for (int n = 1; n <= j; n++) {dp[m][n] = dp[m-1][n] + dp[m][n-1];}}return dp[i][j];
}

通过上面两个例子，应该就比较清楚怎么玩DP了，不懂的话可以继续往下看：

案例3：二维数组形式

问题描述：给定一个包含非负整数的 m x n 网格，每次只能向下或者向右移动一步，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

举例：
输入:
arr = [[1,3,1],[1,5,1],[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

第一步骤：定义数组元素的含义

求什么问题，就定义什么含义，我们的问题是要求从(0,0)到达（2，2）坐标下的路径数字和最小。所以定义 dp[i] [j] 的含义为：从(0,0)到达（i，j）坐标下的路径最小数字和。

第二步骤：找出数组元素之间的关系式

我们可以从目标出发，去找关系，怎么找，是最核心最难的一个，dp[i] [j]究竟会等于什么呢？对于这道题，由于机器人可以向下走或者向右走，所以有两种方式到达从 (i-1, j) 这个位置走一步到达
从 (i, j-1) 这个位置走一步到达我们是要算所有路径下的数字和最小值，所以有dp[i] [j] =min{dp[i-1] [j],dp[i] [j-1]} +arr[i][j]

第三步骤：找出初始值

由于递推关系中的分别有（i，j）， （i-1，j），（i，j-1），两个都取最小值时有（i-1，j-1）
由于我们的问题最小是求dp[0][0],令最小值（i-1，j-1）为（0，0）时，有i=1，j=1。
所以初始值为dp[1][0]，dp[0][1]，但除了递推公式的初值，我们知道递推公式只能推出dp[m][n],其中m>=1,n>=1
所以dp[m][0]，dp[0][n],dp[0][0]并不能由递推公式求出，所以特殊处理由于dp[1][0]，dp[0][1]分别包含在dp[m][0]，dp[0][n]中，我们就不用单独求了
显然，dp[0][0]=1, 
dp[m][0]=arr[0][0]+...arr[m][0], 
dp[0][n]=arr[0][0]+...arr[0][n],

代码：

int uniquePaths(int i, int j){int dp[i+1][j+1] ={0}; // // 初始化dp[0][0]=0;for(int m = 1; m <= i; m++)  dp[m][0] = dp[m-1][0]+arr[m-1][0];for(int n = 1; n <= j; n++)  dp[0][n] = dp[0][n-1]+arr[0][n-1];// 通过关系式来计算出 dp[i][j]for (int m = 1; m <= i; m++) {for (int n = 1; n <= j; n++) {dp[m][n] = min(dp[m-1][n],dp[m][n-1])+arr[m][n];}}return dp[i][j];
}

参考资料：告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文）