一、完整代码（精简注释）
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int row = grid.size(), col = grid[0].size(); // dp[i][j] 表示到达 (i,j) 的最小路径和 vector<vector<int>> dp(row, vector<int>(col, 0)); // 初始化起点 dp[0][0] = grid[0][0]; // 初始化第一列，只能从上方到达 for (int i = 1; i < row; i++) { dp[i][0] = grid[i][0] + dp[i-1][0]; } // 初始化第一行，只能从左方到达 for (int j = 1; j < col; j++) { dp[0][j] = grid[0][j] + dp[0][j-1]; } // 从上方和左方选择较小的路径和 for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[row-1][col-1]; } };二、动态规划五步总结
1. 确定 dp 数组及下标含义
dp[i][j] 表示从左上角 (0,0) 出发，到达位置 (i,j) 时的最小路径和。
例如：
dp[2][3] 表示从 (0,0) 到 (2,3) 的最小路径和。
注意：dp 数组记录的是到达当前位置的最小路径和，而不是当前位置的原始数值。
2. 确定状态转移方程
题目规定只能向右或者向下移动。
因此，到达当前位置 (i,j) 只有两种方式：
从上方 (i-1,j) 向下移动。
从左方 (i,j-1) 向右移动。
为了得到最小路径和，需要比较上方和左方的路径和，选择较小的一个，再加上当前位置的数值。
状态转移方程：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];其中：
dp[i-1][j]：从上方到达的最小路径和。
dp[i][j-1]：从左方到达的最小路径和。
grid[i][j]：当前位置的数值。
核心思想：当前位置的最优解，由上方和左方已经计算好的最优解推导得到。
3. 初始化 dp 数组
由于第一行和第一列只有一种移动方向，因此需要单独初始化。
（1）初始化起点
dp[0][0] = grid[0][0];（2）初始化第一列
for (int i = 1; i < row; i++) { dp[i][0] = grid[i][0] + dp[i-1][0]; }第一列只能从上往下移动，因此当前值等于上方路径和加上当前位置的数值。
（3）初始化第一行
for (int j = 1; j < col; j++) { dp[0][j] = grid[0][j] + dp[0][j-1]; }第一行只能从左往右移动，因此当前值等于左方路径和加上当前位置的数值。
4. 确定遍历顺序
for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } }遍历顺序：从上到下、从左到右。
原因：
计算 dp[i][j] 时，需要使用上方的 dp[i-1][j] 和左方的 dp[i][j-1]。
因此必须保证这两个位置已经计算完成。
由于第一行和第一列已经初始化，所以剩余位置从 (1,1) 开始遍历即可。
5. 举例推导 dp 数组
假设原始数组：
grid: 1 3 1 1 5 1 4 2 1第一步：初始化起点、第一行和第一列。
dp: 1 4 5 2 ? ? 6 ? ?第二步：计算剩余位置。
dp[1][1] = min(4, 2) + 5 = 7; dp[1][2] = min(5, 7) + 1 = 6; dp[2][1] = min(7, 6) + 2 = 8; dp[2][2] = min(6, 8) + 1 = 7;最终得到：
dp: 1 4 5 2 7 6 6 8 7因此最小路径和为 7。
对应路径：
1 -> 3 -> 1 -> 1 -> 1三、复杂度分析
时间复杂度：O(m * n)
因为需要遍历整个二维数组，每个位置只计算一次。
空间复杂度：O(m * n)
因为创建了一个 m 行 n 列的二维 dp 数组存储路径和。
四、核心总结
本题属于二维动态规划中的网格路径问题。
dp[i][j] 表示从起点到当前位置的最小路径和。
第一行只能从左边到达，第一列只能从上边到达，因此需要单独初始化。
对于其他位置，只需要比较上方和左方的最小路径和，选择较小值，再加上当前位置的数值。
遍历顺序为从上到下、从左到右，保证计算当前位置时，所依赖的状态已经计算完成。
最终返回 dp[row-1][col-1]，即从左上角到右下角的最小路径和。
与「不同路径」的区别
不同路径：
dp[i][j] = dp[i-1][j] + dp[i][j-1];计算的是到达当前位置的路径总数。
最小路径和：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];计算的是到达当前位置的最小路径代价。
最终记忆：不同路径求方案数量，最小路径和求最优代价。两者都是通过上方和左方的状态推导当前位置的状态。
