C++代码解题:用动态规划解决给定一个包含非负整数的 3*3网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。请写出解题思路
时间: 2024-03-10 21:44:35 浏览: 24
这是一个经典的动态规划问题。我们可以定义一个二维数组 dp,其中 dp[i][j] 表示从起点 (0, 0) 到达网格中 (i, j) 位置的最小路径和。对于第一行和第一列,由于每个位置只有一条路径可以到达,因此可以直接累加计算。对于其他位置,可以从上方和左方到达当前位置,因此可以选择路径和较小的一个方向,即:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
最后,dp[2][2] 就是答案。整个算法的时间复杂度为 O(9) = O(1),因为网格大小是固定的 3*3。
下面是 C++ 代码实现:
```cpp
int minPathSum(vector<vector<int>>& grid) {
int dp[3][3];
dp[0][0] = grid[0][0];
for (int i = 1; i < 3; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < 3; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < 3; i++) {
for (int j = 1; j < 3; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[2][2];
}
```