C++代码解题:给定一个包含非负整数的 3*3网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。代码要带注释
时间: 2024-03-13 08:44:45 浏览: 162
给定一个包含非负整数的M x N网格,请找出一条从左上角到右下角的路径,使得路径的数字总和最小,并显示其路径。
5星 · 资源好评率100%
好的,这是一个经典的动态规划问题,可以使用DP求解。以下是C++代码及注释:
```c++
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(); // 网格的行数
int n = grid[0].size(); // 网格的列数
// 初始化第一行和第一列
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
}
for (int j = 1; j < n; j++) {
grid[0][j] += grid[0][j - 1];
}
// 从(1,1)开始遍历网格,计算到达每个网格的最小路径和
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]); // 选择上方或左方的最小值
}
}
return grid[m - 1][n - 1]; // 返回从左上角到右下角的最小路径和
}
```
注释中已经说明了每个步骤的作用,主要思路是动态规划,先初始化第一行和第一列,然后从(1,1)开始遍历网格,计算到达每个网格的最小路径和,最后返回从左上角到右下角的最小路径和。
阅读全文