企业官网建设流程全解析

64. 最小路径和 - 力扣（LeetCode）

题目描述

给定一个包含非负整数的m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解题思路

经典网格动态规划，只能向右、向下走。

1. 状态定义dp[i][j]：走到网格第(i,j)位置的最小路径和。

dp 数组做边界扩容：dp 大小(m+2)*(n+2)，多余边界填充极大值，避免越界判断。 原网格下标从 0 开始，dp 从 1 开始，grid[i‑1][j‑1]对应 dp 的i,j。

1. 状态转移方程到达dp[i][j]只能来自上方dp[i‑1][j]或者左边dp[i][j‑1]，取两者较小值，再加上当前格子权重
2. 初始化边界全部填充一个很大的数1000000，代表不可达；dp[0][1]=0作为起点的触发条件，让dp[1][1]可以正确拿到 grid [0][0] 的值。
3. 结果dp[m][n]就是到达右下角的最小路径和。

class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m + 2, vector<int>(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]; } };