写在最前面
当时大学开的那么多算法课为啥一节都不好好听讲！
什么是动态规划
动态规划，是一种解决棘手问题的方法，它将问题分成小问题，并从解决小问题作为起点，从而解决最终问题的一种方法。
看不明白没关系，后面我们会从几个实例中逐渐让大家摸清规律。
问题一 爬梯子问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
- 示例 1：
输入： 2
输出： 2 解释： 有两种方法可以爬到楼顶。- 1 阶 + 1 阶
- 2 阶
- 示例 2：
输入： 3
输出： 3 解释： 有三种方法可以爬到楼顶。- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
你可能会这么想
走1阶台阶只有一种走法，但是走2阶台阶有两种走法（如示例1），如果n是双数，我们可以凑成m个2级台阶，每个m都有两种走法，如果n是单数，那么我们可以凑成m个2级台阶加上一个1级台阶，这样就似乎于一个排列组合题目了，但是开销貌似比较大。
如何将整个问题化成一个一个的小问题
这个时候使用动态规划就很有用，因为这个问题其实是由一个很简单的小问题组成的。 观察这种小问题，简单地我们可以采用首位或者中间态进行一次分析，比如我们从最终态进行分析：
走N阶台阶，最后一步必定是1步或者2步到达。
那么N阶台阶的走法不就相当于最后走一步和最后走两步的走法的总和吗？换一种方式来说，我们取一个中间态：如果总共有3级台阶，3级台阶的走法只会存在两种大的可能：走了1阶台阶+走两步、走了两级台阶+走一步，即3级台阶的所有走法就是走了1阶台阶的走法加上走了2阶台阶的走法，而1阶台阶的走法只有一种，2阶台阶的走法有2种，所有3阶台阶的走法有3种,我们使用一种更通用的方式进行表达的话就是所谓的状态转换方程：
有了这个公式，我们就可以使用迭代来完成整个过程，寻求到最终的ways[n]的值了，迭代的开始即我们已知的确定条件：一阶台阶只有一种走法：ways[1]=1、两阶台阶有两种走法：ways[2]=2，代码如下：
实现代码
public int climbStairs(int n) { if(n==1){ return 1; }else if(n==2){ return 2; } //避免使用0，即下标从1开始，更好理解 int ways[]=new int[n+1]; //赋值迭代初始条件 ways[1]=1; ways[2]=2; //利用状态转换方式进行迭代 for(int i=3;i<=n;i++){ ways[i]=ways[i-1]+ways[i-2]; } return ways[n];}复制代码 基本流程
从上面的解决途径我们可以发现基本流程是这样的：
- 从一个现实方案中找到状态转换的特有规律
- 从特有规律中提取出状态转换方程
- 找到状态转换方程的迭代初始值（确定值）
- 解决问题
问题二 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
- 示例 1:
输入: m = 3, n = 2
输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
- 示例 2:
输入: m = 7, n = 3
输出: 28解决方法
相信沿用问题一的套路很多人已经知道该怎么办了，从一个二维数组的左上（0，0）走到右下（m,n）有多少种走法，且只能往右和往下走，那么如果要走到（m,n），那么我们的上一步只能是（m-1,n）或者（m,n-1），所以走到（m,n）的所有走法就是走到（m-1,n）的所有走法+走到(m,n-1)的所有走法，即可以得到状态转换方程：
但是，这个问题还有一些其他的问题限制需要我们考虑到，即走到两侧的时候，只会有一个方向的走法，（上方只会有ways[m-1][n]一个方式，左侧只会有ways[m][n-1]一个方式）即下图：
我们需要对这两种方式进行限制，在这里我在外围再扩展了一圈，将整个方格扩展为**(m+1)*(n+1)**的方格，来避开限制，当然也可以直接限制（后续会讲到），但是将其所有的值都设置为0，即相当于设置了限制。
实现代码
public static int uniquePaths(int m, int n) { int[][] ways=new int[m+1][n+1]; //上方扩展一行，使其值为0 for(int i=0;i<=n;i++){ ways[0][i]=0; } //边上扩展一列，使其值为0 for(int j=0;j<=m;j++){ ways[j][0]=0; } //设置初始值，起点走法为1，只能一步一步走 ways[1][1]=1; for(int a=1;a<=m;a++){ for(int b=1;b<=n;b++){ if(a==1&&b==1){ continue; } //套用状态转换方程 ways[a][b]=ways[a][b-1]+ways[a-1][b]; } } return ways[m][n];}复制代码 问题三 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
- 示例:
输入:
[ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。解决方法
这个问题与问题二及其相似，但是其涉及到一个最优解的问题，现在每一个点都有一个类似权重的值，我们要使这个值最小，其实用问题二的想法，我们很快就能得到答案：走到(m,n)只能从(m-1,n)和(m,n-1)两个地方走过来，那么要保证(m,n)的权重最小，那么我们只需要选择走到(m-1,n)和（m，n-1）权重较小的那一边即可，那么我们就可以得到新的状态转移方程：
即 走到当前点的权重=走到前一步权重的较小值+当前点的权重 ，并且该问题也有针对边上元素的特殊处理
代码
public static int minPathSum(int[][] grid) { //权重存储数组 int[][] sum=new int[grid.length][grid[0].length]; //起点初始权重确定值 sum[0][0]=grid[0][0]; for(int i=0;i 问题四 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
- 例如，给定三角形：
[
[2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。解决方法
这个问题可以理解为问题三的变种，但是他没有一个固定的终点，因为我们之前的方法都是从最后一步开始分析的，所以很多人也就对该问题无从下手了。但是其实我们也可以将最后一行的任何一个元素作为终点，因为该问题起点确定，并且终点必定在最后一行。但是为了代表性，我们还是选取1或8为例子，如果最终达到1，需要上一排达到6或5。如果要达到5，那么需要上一排达到3或4，所以我们由此可以得到该问题的状态转移方程：
这样我们就可以根据问题三的模式找到达到最后一排所有可能终点（4，1，8，3）的最小权重，我们再从所有权重中选取最小值即可,该问题也有针对边上元素的特殊处理。
实现代码
public static int minimumTotal(List
> triangle) { //创建状态存储数组 int[][] sum=new int[triangle.size()][triangle.size()]; //起点确定，权重确定 sum[0][0]=triangle.get(0).get(0); for(int i=0;i
动态规划可用的总结
（参考《算法图解》）
- 需要在给定约束条件下优化某种指标时，动态规划很有用。
- 问题可分解为离散子问题时，可使用动态规划来解决。
- 每种动态规划解决方案都涉及网格。
- 单元格中的值通常就是你要优化的值。
- 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
- 没有放之四海皆准的计算动态规划解决方案的公式。