64. 最小路径和 - 力扣LeetCode题目描述给定一个包含非负整数的m x n网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。解题思路经典网格动态规划只能向右、向下走。状态定义dp[i][j]走到网格第(i,j)位置的最小路径和。dp 数组做边界扩容dp 大小(m2)*(n2)多余边界填充极大值避免越界判断。 原网格下标从 0 开始dp 从 1 开始grid[i‑1][j‑1]对应 dp 的i,j。状态转移方程到达dp[i][j]只能来自上方dp[i‑1][j]或者左边dp[i][j‑1]取两者较小值再加上当前格子权重初始化边界全部填充一个很大的数1000000代表不可达dp[0][1]0作为起点的触发条件让dp[1][1]可以正确拿到 grid [0][0] 的值。结果dp[m][n]就是到达右下角的最小路径和。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); vectorvectorint dp(m 2, vectorint(n 2, 1000000)); dp[0][1]0; for (int i 1; i m 1; i) { for (int j 1; j n 1; j) { dp[i][j] min(dp[i][j - 1], dp[i - 1][j]) grid[i - 1][j - 1]; } } // 遍历打印dp数组 for (int i 0; i dp.size(); i) { for (int j 0; j dp[i].size(); j) { cout dp[i][j] \t; } cout endl; } return dp[m][n]; } };