最小路径和可通过动态规划求解，定义dpi为从起点到(i,j)的最小和，状态转移方程为dpi=gridi+min(dpi-1,dpi)，初始化第一行和第一列后遍历填充，最终结果为dpm-1。
在C++中实现动态规划求解“最小路径和”问题，通常应用于二维网格中从左上角到右下角的路径选择。目标是找出一条路径，使得路径上所有数字的和最小，每次只能向下或向右移动。
问题描述
给定一个 m × n 的非负整数网格 grid，找出从左上角到右下角的路径，使得路径上的数字总和最小。只能向下或向右移动。动态规划思路
使用动态规划来避免重复计算。定义 dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的最小路径和。 状态转移方程：- dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
- 第一行：只能从左向右走，dp[0][j] = dp[0][j-1] + grid[0][j]
- 第一列：只能从上向下走，dp[i][0] = dp[i-1][0] + grid[i][0]
C++ 实现代码
可以直接在原数组上修改以节省空间，或者创建一个新的 dp 数组。以下是使用原数组进行空间优化的版本：代码示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
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}
};
cout << "最小路径和: " << minPathSum(grid) << endl;
return 0;
}
复杂度分析
时间复杂度：O(m × n)，需要遍历整个网格一次。空间复杂度：O(1)，直接在原数组上修改，没有使用额外空间（如果不允许修改原数组，则需 O(m × n)）。
基本上就这些。这种方法简洁高效，适合大多数最小路径和类题目。注意边界判断和初始化顺序即可。
