02二维动态规划
# 02 二维动态规划
# 64 最小路径和 (opens new window)
给定一个 m × n 大小的非负整数矩阵，求从左上角开始到右下角结束的、经过的数字的和最小的路径。每次只能向右或者向下移动。
输入是一个二维数组，输出是最优路径的数字和。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
解析:
设置状态：使用一个二维的 dp 数组，其中 dp[i][j] 表示从左上角开始到 (i, j) 位置的最
优路径的数字和。
状态转移方程：因为每次只能向下或者向右移动，我们可以很容易得到状态转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid 表示原数组。
边界条件：只有一格dp[0][0] = grid[0][0]；第一行的元素只能由前一个元素向右移动得到即dp[0][j] = dp[0][j-1]+grid[0][j]；第一列的元素只能由上一个元素向下移动得到即dp[i][0] = dp[i-1][0]+grid[i][0]
class Solution {
public:
int minPathSum_old(vector<vector<int>>& grid) {
int ans = 0;
if(grid.empty()||grid[0].empty()){
return ans;
}
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m,vector<int>(n));
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(i==0&&j==0){
dp[i][j] = grid[0][0];
}else if(i==0){
dp[i][j] = dp[i][j-1] + grid[i][j];
}else if(j==0){
dp[i][j] = dp[i-1][j] + grid[i][j];
}else{
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
}
}
}
return dp[m-1][n-1];
}
};
因为 dp 矩阵的每一个值只和左边和上面的值相关，我们可以使用空间压缩将 dp 数组压缩为一维。对于第 i 行，在遍历到第 j 列的时候，因为第 j-1 列已经更新过了，所以 dp[j-1] 代表 dp[i][j-1]的值；而 dp[j] 待更新，当前存储的值是在第 i-1 行的时候计算的，所以代表 dp[i-1][j]的值。
# 542 01矩阵 (opens new window)
给定一个由 0 和 1 组成的二维矩阵，求每个位置到最近的 0 的距离。
输入是一个二维 0-1 数组，输出是一个同样大小的非负整数数组，表示每个位置到最近的 0的距离。
输入：mat = [[0,0,0],[0,1,0],[1,1,1]] 输出：[[0,0,0],[0,1,0],[1,2,1]]
解析:
本题涉及到四个方向上的最近搜索，如果使用递归的方法进行搜索在二维数组中将造成极大的时间复杂度。使用动态规划进行存储化，可以使得递归搜索不会重复遍历相同位置；另一种更简单的方法是，从左上到右下进行一次动态搜索，再从右下到左上进行一次动态搜索，这样两次动态搜索即可完成四个方向上的查找。
设置状态：使用一个二维数组 dp[i][j] 表示位置为 (i,j) 的元素与0的距离
状态转移方程：值为0的元素到0的距离为0；从左上到右下进行动态搜索，那么dp[i][j] 可以从dp[i-1][j]、dp[i][j-1]和自身三个状态中转移得到dp[i][j]=min(dp[i][j],min(dp[i-1][j],dp[i][j-1])) + 1； 从右下到左上进行动态搜索的状态转移方程可以类比得到dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j+1])) + 1
边界情况：当d[i][j]处于矩阵的边界上时其状态转移受到限制，例如，从左上到右下进行动态搜索时处于第一行的元素状态仅能从自身和前一个状态转移得到，而第一列的元素状态仅能从自身和上一个状态转移得到。
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
if(mat.empty()||mat.empty()){
return {};
}
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m, vector<int>(n,INT_MAX-1)); // INT_MAX会在特殊用例中报错
// 从左上到右下进行动态搜索
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(mat[i][j]==0){
dp[i][j] = 0;
}else{
// 区分边界情况
if(j>0){
dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
}
if(i>0){
dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
}
}
}
}
// 从右下到左上进行动态搜索
for(int i=m-1;i>=0;--i){
for(int j=n-1;j>=0;--j){
if(mat[i][j]){
if(j<n-1){
dp[i][j] = min(dp[i][j], dp[i][j+1]+1);
}
if(i<m-1){
dp[i][j] = min(dp[i][j], dp[i+1][j]+1);
}
}
}
}
return dp;
}
};
# 221 最大正方形 (opens new window)
给定一个二维的 0-1 矩阵，求全由 1 构成的最大正方形面积。
输入是一个二维 0-1 数组，输出是最大正方形面积。
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4
解析:
对于在矩阵内搜索正方形或长方形的题型，一种常见的做法是定义一个二维 dp 数组，其中dp[i][j]表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题，则表示以 (i, j) 为右下角的全由 1 构成的最大正方形面积。
设置状态：定义一个二维 dp 数组，其中dp[i][j]表示以 (i, j) 为右下角的全由 1 构成的最大正方形面积
状态转移方程：如果当前位置是 0，那么 dp[i][j] 即为 0；如果当前位置是 1，我们假设 dp[i][j] = k^2 ，其充分条件为 dp[i-1][j-1]、dp[i][j-1]和 dp[i-1][j]的值必须都不小于 (k − 1)^2 ，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。同理，如果这三个值中的最小值为 k − 1，则 (i, j) 位置一定且最大可以构成一个边长为 k 的正方形。所以状态转移方程为dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1
初始情况：仅有一个方格构成正方形dp[0][0] = 1
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty()||matrix[0].empty()){
return 0;
}
int m = matrix.size(), n = matrix[0].size();
int maxSize = 0;
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(matrix[i-1][j-1] == '1'){
dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
}
maxSize = max(dp[i][j],maxSize);
}
}
return maxSize * maxSize;
}
};