BM68. 矩阵的最小路径和
描述
示例1
输入:
[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
输出:
12
示例2
输入:
[[1,2,3],[1,2,3]]
输出:
7
C++ 解法, 执行用时: 2ms, 内存消耗: 324KB, 提交时间: 2022-01-25
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
int minPathSum(vector<vector<int> >& matrix) {
// write code here
int rowls = matrix.size();
int cols = matrix[0].size();
for (int i =0;i< rowls;i++)
{
for(int j=0;j< cols;j++)
{
if (i==0 && j>0)
matrix[i][j] = matrix[i][j] + matrix[i][j - 1];
else if (j == 0 && i> 0)
{
matrix[i][j] = matrix[i -1][j] + matrix[i][j];
}
else{
if (i ==0 && j==0) continue;
int min_v = matrix[i][j-1] > matrix[i-1][j]?matrix[i-1][j]:matrix[i][j-1];
matrix[i][j] = matrix[i][j] + min_v;
}
}
}
return matrix[rowls -1][cols-1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2021-04-04
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
int minPathSum(vector<vector<int> >& matrix) {
// write code here
int n = matrix.size();
int m = matrix[0].size();
for(int i = 1 ; i < n ; i++){matrix[i][0] = matrix[i-1][0]+ matrix[i][0];}
for(int j = 1 ; j < m ; j++){matrix[0][j] = matrix[0][j-1]+ matrix[0][j];}
for(int i = 1 ; i < n ; i++)
{
for(int j = 1 ; j < m ; j++)
{
matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j];
}
}
return matrix[n-1][m-1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-04-30
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
int minPathSum(vector<vector<int> >& matrix) {
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0)
continue;
if (i == 0) {
//第一行只能从左边走过来
matrix[i][j] += matrix[i][j - 1];
} else if (j == 0) {
//第一列只能从上面走下来
matrix[i][j] += matrix[i - 1][j];
} else {
//递推公式，取从上面走下来和从左边走过来的最小值+当前坐标的值
matrix[i][j] += min(matrix[i - 1][j], matrix[i][j - 1]);
}
}
}
return matrix[m - 1][n - 1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-04-04
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
int minPathSum(vector<vector<int> >& matrix) {
// write code here
int m=matrix.size();
int n=matrix[0].size();
int dp[m][n];
dp[0][0]=matrix[0][0];
for(int i=1;i<n;i++){
dp[0][i]=matrix[0][i]+dp[0][i-1];
}
for(int j=1;j<m;j++){
dp[j][0]=matrix[j][0]+dp[j-1][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=matrix[i][j]+min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2021-04-25
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>> the matrix
* @return int整型
*/
int minPathSum(vector<vector<int> >& matrix) {
// write code here
//动态规划，需要用到辅助表，辅助表表示从（0，0）点到（i，j）经过的最短路径之和
//关键在于生成辅助表：
/*
对辅助表的第一行所有位置来说，即(0，j)(0≤j<N)，
从(0，0)位置走到(0，j)位置只能向右走，
所以(0，0)位置到(0，j)位置的路径和就是m[0][0..j]这些值的累加结果。
同理，对于辅助表的第一列的所有位置来说，同第一行的处理方式相同。
对于除了第一列和第一行的其他所有辅助表元素来说，（i，j）都由
左边位置（i-1，j)和上边位置(i,j-1)两者中的最小值和（i，j）相加得到
*/
int raw=matrix.size();//二维矩阵的行数
int column=matrix[0].size();//二维矩阵的列数
//对距离矩阵的列进行处理
for(int i=1;i<raw;++i)
{
matrix[i][0]=matrix[i-1][0]+matrix[i][0];
}
for(int i=1;i<column;++i)
{
matrix[0][i]=matrix[0][i-1]+matrix[0][i];
}
for(int i=1;i<raw;++i)
{
for(int j=1;j<column;++j)
{
matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j];
}
}
return matrix[raw-1][column-1];
}
};