【Hot 100 刷题计划】 LeetCode 64. 最小路径和 | C++ 二维动态规划基础版

LeetCode 64. 最小路径和

📌 题目描述

题目级别：中等

给定一个包含非负整数的m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

• 示例 1:
  输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
  输出：7
  解释：因为路径 1 → 3 → 1 → 1 → 1 的总和最小。

💡 破题思路：网格类 DP 模板

这道题是经典的网格动态规划。因为机器人每次只能向右或者向下走，这就意味着到达任意一个格子(i, j)，它只能是从上方(i-1, j)走下来，或者是从左方(i, j-1)走过来。

状态定义：
定义dp[i][j]为：从左上角走到格子(i, j)的最小路径和。

状态转移方程：
既然只有两条路过来，想要当前格子的路径和最小，我们就看看上方和左方哪个格子的路径和更小，挑那个小的走过来，再加上当前格子本身的代价。

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

边界条件初始化：

1. 起点：dp[0][0] = grid[0][0]。
2. 第一行：只能从左边一直走过来，所以dp[0][j] = dp[0][j-1] + grid[0][j]。
3. 第一列：只能从上边一直走下来，所以dp[i][0] = dp[i-1][0] + grid[i][0]。

💻 C++ 代码实现 (严谨边界处理)

classSolution{public:intminPathSum(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();// 规范写法：使用 vector 开辟 2D DP 数组vector<vector<int>>dp(m,vector<int>(n,0));for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(i==0&&j==0){// 起点dp[i][j]=grid[i][j];}elseif(i==0){// 第一行，只能从左边来dp[i][j]=grid[i][j]+dp[i][j-1];}elseif(j==0){// 第一列，只能从上面来dp[i][j]=grid[i][j]+dp[i-1][j];}else{// 中间格子，取上和左的较小值dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}}returndp[m-1][n-1];}};