动态规划-最小路径和-空间压缩
问题描述
给定一个二维数组 matrix ,Bob 必须从左上角出发,最后到达右下角,沿途只可以向下或者向右走。沿途的数字的累加就是距离累加和。返回最小距离累加和。
暴力递归
常规题型,不再赘述。
int process(const vector<vector<int>> &matrix, int x, int y)
{
if(x < 0 || x >= matrix[0].size() || y < 0 || y >= matrix.size())
return INT_MAX;
if(x == matrix[0].size() - 1 && y == matrix.size() - 1)
return matrix[y][x];//可别写成了[x][y]
int down = process(matrix, x, y + 1);
int right= process(matrix, x + 1, y);
return matrix[y][x] + std::min(down, right);
}
int minPathSum(const vector<vector<int>> &matrix)
{
return process(matrix, 0, 0);
}
动态规划
int help(const vector<vector<int>> &matrix, const vector<vector<int>> &dp, int x, int y)
{
if(x < 0 || x >= matrix[0].size() || y < 0 || y >= matrix.size())
return INT_MAX;
if(x == matrix[0].size() - 1 && y == matrix.size() - 1)
return matrix[y][x];
return dp[y][x];
}
int minPathSum(const vector<vector<int>> &matrix)
{
vector<vector<int>> dp(matrix[0].size(), vector<int>(matrix.size(), 0));
for(int r = matrix.size() - 1; r >= 0; r--)
{
for(int c = matrix[0].size() - 1; c >= 0; c--)
{
int down = help(matrix, dp, c, r + 1);
int right= help(matrix, dp, c + 1, r);
dp[r][c] = matrix[r][c] + std::min(down, right);
}
}
return dp[0][0];
}
空间压缩
滚动数组最常见的是空间压缩。本题的 dp 表中每个格子只依赖右边和下面的格子:
填表顺序为从下到上,从右到左。因为每个格子只依赖紧邻的右边和下边的格子,所以 dp 表可以压缩成单行,后续填表仅在这一行表格上滚动更新即可。其他说明参见代码:
int minPathSum(const vector<vector<int>> &matrix)
{
int row = matrix.size() - 1;
int col = matrix[0].size() - 1;
vector<int> dp(matrix[0].size(), 0);
//特例初始化
dp[col] = matrix[row][col];//初始时刻dp为最后一行,且末尾格子为matrix[row][col];
for(int c = col - 1; c >= 0; c--)
{
dp[c] = matrix[row][c] + dp[c+1];//初始化最后一行
}
for(int r = row - 1; r >= 0; r--)//从倒数第二行开始滚动打表
{
for(int c = col; c >= 0; c--)//从右往左打表
{
dp[c] = matrix[r][c] + std::min(dp[c], c == col ? INT_MAX : dp[c+1]);//注意边界条件
}
}
return dp[0];
}
总结
- 空间压缩时最好不要使用统一处理法,而应该用特例初始化,先把初始条件加载好再进行数组的滚动。
- 没必要压缩空间,容易出错。
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧