C++代码解题:给定一个包含非负整数的 3*3网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。代码要带注释
时间: 2024-03-06 12:50:58 浏览: 44
以下是C++代码解题:
```cpp
#include <iostream>
#include <vector>
using namespace std;
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];
}
// 计算其他位置的最小路径和
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]; // 返回右下角的最小路径和
}
int main() {
vector<vector<int>> grid = {{1,3,1}, {1,5,1}, {4,2,1}};
int minSum = minPathSum(grid);
cout << minSum << endl; // 输出最小路径和 7
return 0;
}
```
注释说明:
1. 首先定义一个函数 `minPathSum` 来计算最小路径和。该函数接受一个二维向量 `grid` 作为输入参数。
2. 获取输入网格的行数 `m` 和列数 `n`。
3. 初始化第一行和第一列的最小路径和,因为只能向下或向右移动,所以第一行和第一列的最小路径和就是前一个位置的最小路径和加上当前位置的值。
4. 计算其他位置的最小路径和,对于每个位置,它的最小路径和就是从上面或左边的位置中选择一个最小的,再加上当前位置的值。
5. 返回右下角的最小路径和作为函数的输出。
6. 在 `main` 函数中,定义一个二维向量 `grid` 作为输入网格,并调用 `minPathSum` 函数来计算最小路径和。
7. 输出最小路径和。