上一次
解释了动态规划的一些基本特性和解题思路，也说了动态规划其实就是记住之前问题的答案，然后利用之前问题的答案来分析并解决当前问题，这里面有两个非常重要的步骤，就是
拆解问题
和
定义状态
。
这次来针对具体的一类动态规划问题，矩阵类动态规划问题，来看看针对这一类问题的思路和注意点。
矩阵类动态规划，也可以叫做坐标类动态规划，一般这类问题都会给你一个矩阵，矩阵里面有着一些信息，然后你需要根据这些信息求解问题。
其实
矩阵可以看作是图的一种，怎么说？你可以把整个矩阵当成一个图，矩阵里面的每个位置上的元素当成是图上的节点，然后每个节点的邻居就是其相邻的上下左右的位置
，我们遍历矩阵其实就是遍历图，在遍历的过程中会有一些临时的状态，也就是子问题的答案，我们记录这些答案，从而推得我们最后想要的答案。
一般来说，在思考这类动态规划问题的时候，我们只需要思考当前位置的状态，然后试着去看当前位置和它邻居的递进关系，从而得出我们想要的递推方程，这一类动态规划问题，相对来说比较简单，我们通过几道例题来熟悉一下。
LeetCode 第 62 号问题：
不同路径。
题目描述
一个机器人位于一个
m x n
网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：
m
和
n
的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
题目解析
给定一个矩阵，问有多少种不同的方式从起点(0,0) 到终点 (m-1,n-1)，并且每次移动只能向右或者向下，我们还是按之前提到的分析动态规划那四个步骤来思考一下：
-
问题拆解
题目中说了，每次移动只能是向右或者是向下，矩阵类动态规划需要关注当前位置和其相邻位置的关系，对于某一个位置来说，经过它的路径只能从它上面过来，或者从它左边过来，因此，如果需要求到达当前位置的不同路径，我们需要知道到达其上方位置的不同路径，以及到达其左方位置的不同路径
-
状态定义
矩阵类动态规划的状态定义相对来说比较简单，只需要看当前位置即可，问题拆解中，我们分析了当前位置和其邻居的关系，提到每个位置其实都可以算做是终点，状态表示就是 “
从起点到达该位置的不同路径数目
”
-
递推方程
有了状态，也知道了问题之间的联系，其实递推方程也出来了，就是
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
-
实现
有了这些，这道题还没完，我们还要考虑状态数组的初始化问题，对于上边界和左边界的点，因为它们只能从一个方向过来，需要单独考虑，比如上边界的点只能从左边这一个方向过来，左边界的点只能从上边这一个方向过来，它们的不同路径个数其实就只有 1，提前处理就好。
参考代码
//www.cxyxiaowu.com
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i m; ++i) {
dp[i][0] = 1;
}
for (int j = 0; j
n; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i m; ++i) {
for (int j = 1; j n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
LeetCode 第 63 号问题：
不同路径II
题目描述
一个机器人位于一个
m x n
网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物
。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
题目解析
在上面那道题的基础上，矩阵中增加了障碍物，这里只需要针对障碍物进行判断即可，如果当前位置是障碍物的话，状态数组中当前位置记录的答案就是 0，也就是没有任何一条路径可以到达当前位置，除了这一点外，其余的分析方法和解题思路和之前
一样
。
参考代码
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int
[m][n];
dp[0][0] = 1;
for (int i = 1; i dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
}
for (int i = 1; i dp[0][i] = obstacleGrid[0][i] == 1 ? 0 : dp[0][i - 1];
}
for (int i = 1; i for (int j = 1; j dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
LeetCode 第 64 号问题：
最小路径和
题目描述
给定一个包含非负整数的
m
x
n
网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：
每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
题目解析
给定一个矩阵，问从起点(0,0) 到终点 (m-1,n-1) 的最小路径和是多少，并且每次移动只能向右或者向下，按之四个步骤来思考一下：
-
问题拆解
拆解问题的方式方法和前两道题目非常类似，这里不同的地方只是记录的答案不同，也就是状态不同，我们还是可以仅仅考虑当前位置，然后可以看到只有上面的位置和左边的位置可以到达当前位置，因此当前问题就可以拆解成两个子问题
-
状态定义
因为是要求路径和，因此状态需要记录的是 “
从起始点到当前位置的最小路径和
”
-
递推方程
有了状态，以及问题之间的联系，我们知道了，当前的最短路径和可以由其上方和其左方的最短路径和对比得出，递推方程也可以很快写出来：
dp[i][j] = Math.min(dp[i - 1][j] + dp[i][j - 1]) + grid[i][j]
-
实现
实现上面需要重点考虑的还是状态数组的初始化，这一步还是和前面两题类似，这里就不过多赘述
参考代码
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i for (int j = 1; j dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
LeetCode 第 221 号问题：
最大正方形。
题目描述
在一个由
0
和
1
组成的二维矩阵内，找到只包含
1
的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
