数据结构与算法题解|动态规划|——矩阵型动态规划
如果一个问题满足以下两点，那么就可以使用动态规划解决.问题的答案依赖于问题的规模；大规模的问题可以有小规模问题的答案递推得到。
可以使用动态规划的问题的问法一般是三种方式：
求最大值/最小值
求可不可行
求方案总数
本文介绍矩阵型的动态规划的思路和代码。
【leetcode62.不同路径】
一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
题解：
我们令 dp[i][j] 是到达终点的最多路径
动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以初始化为 1。
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 i = 0; i < n; i++)
dp[0][i] = 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];
}
时间复杂度：O(m*n)
空间复杂度：O(m*n)
【leetcode64.最小路径和】
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
题解：
建一个额外的 dp数组，与原矩阵大小相同。在这个矩阵中，dp(i, j)表示从坐标 (i, j)到右下角的最小路径权值。我们初始化右下角的 dp值为对应的原矩阵值，然后去填整个矩阵，对于每个元素考虑移动到右边或者下面。
当左边和上边都不是矩阵边界时：
dp[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
当只有左边是矩阵边界时： 只能从上面来
dp[i][j] = dp[i][j-1]+grid[i][j]
当只有上边是矩阵边界时： 只能从左面来
dp[i][j] = dp[i-1][j]+grid[i][j]
当左边和上边都是矩阵边界时:其实就是起点
dp[i][j] = grid[i][j]
对于每步我们改变的是左上角的值，且之后不会再改变，因此，我们可以使用原数组。
public int minPathSum(int[][] grid) {
for(int i = 0; i < grid.length; i++){
for(int j = 0; j <grid[0].length; j++){
if(i==0 && j!=0){
grid[i][j] = grid[i][j-1]+grid[i][j];
}
else if(i!=0 && j==0){
grid[i][j] = grid[i-1][j]+grid[i][j];
}
else if(i != 0 && j!= 0){
grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
}
return grid[grid.length-1][grid[0].length-1];
}
【leetcode221.最大正方形】
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
题解：
我们用 0 初始化另一个矩阵 dp，维数和原始矩阵维数相同；
dp(i,j) 表示的是由 1 组成的最大正方形的边长；
从 (0,0)开始，对原始矩阵中的每一个 1，我们将当前元素的值更新为
dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1
我们还用一个变量记录当前出现的最大边长，这样遍历一次，找到最大的正方形边长 maxsqlen，那么结果就是 maxsqlen^2。
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = m >0 ?matrix[0].length:0;
//dp[m][n]存正方形面积
int[][] dp = new int[m+1][n+1];
int maxlength = 0;
for(int i = 1; i <= m;i ++){
for(int j = 1; j <= n; j++){
if(matrix[i-1][j-1] == '1'){
dp[i][j] =Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
maxlength = Math.max(maxlength,dp[i][j]);
}
}
}
return maxlength*maxlength;
}
END