动态规划解决最小路径和问题
1. 题目链接
2. 题目描述
给定一个包含非负整数的 m x n 网格 grid，从网格的左上角出发，每次只能向右或向下移动一步，最终到达右下角。要求找到一条路径，使得路径上的数字总和最小。
3. 示例分析
示例输入：
grid = [
[1,3,1],
[1,5,1],
[4,2,1]
]
输出：7
解释：最小路径为 1 → 3 → 1 → 1 → 1，路径和为 1 + 3 + 1 + 1 + 1 = 7。
4. 算法思路
动态规划（Dynamic Programming）
定义 dp[i][j] 表示从起点 (0,0) 到达位置 (i-1,j-1) 的最小路径和。为了简化边界条件的处理，将 dp 数组的维度扩展为 (m+1) x (n+1)，并初始化所有值为 INT_MAX。
状态转移方程
对于每个位置 (i, j)，其最小路径和由上方或左方的最小路径和决定：
dp[i][j] = grid[i-1][j-1] + min(dp[i-1][j], dp[i][j-1])
其中，grid[i-1][j-1] 是当前位置的值，dp[i-1][j] 是上方的路径和，dp[i][j-1] 是左方的路径和。
初始化
dp[0][1] = 0：设置一个虚拟起点dp[0][1]的值为0，使得起点dp[1][1]的值可以正确计算为grid[0][0] + 0。- 其余位置初始化为
INT_MAX，表示尚未计算。
5. 边界条件与注意事项
- 单行或单列网格：当
m=1或n=1时，路径是唯一的，直接累加所有元素即可。 - 索引转换：
dp[i][j]对应网格中的grid[i-1][j-1]，需要注意索引偏移。 - 虚拟起点的作用：通过
dp[0][1] = 0避免了在循环中单独处理起点(1,1)的初始化问题。 - 输入为空的情况：题目假设输入为非空网格，但实际代码中需注意
grid[0].size()可能越界。
6. 代码实现
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][1] = 0; // 虚拟起点，用于初始化 dp[1][1]
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
};
代码解释
- 初始化
dp数组：通过dp[0][1] = 0使得起点(1,1)的值为grid[0][0]。 - 填充
dp数组：遍历每个位置，根据上方和左方的最小值更新当前路径和。 - 返回结果：最终结果存储在
dp[m][n]，表示到达右下角的最小路径和。
复杂度分析
- 时间复杂度：
O(mn)，遍历整个网格。 - 空间复杂度：
O(mn)，使用了(m+1) x (n+1)的dp数组。
通过动态规划方法，能够高效解决二维网格中的最小路径和问题，适用于机器人导航、资源分配等实际场景。