给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。
时间: 2023-12-08 15:20:52 浏览: 107
可以使用动态规划来解决这个问题。假设dp[i][j]表示从左上角走到第i行第j列的位置的最小路径和,则有:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
其中,matrix[i][j]表示第i行第j列的数字。
边界条件为:
dp[0][0] = matrix[0][0]
dp[i][0] = dp[i-1][0] + matrix[i][0]
dp[0][j] = dp[0][j-1] + matrix[0][j]
最终答案为dp[m-1][n-1]。
代码实现:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}