力扣 LCR 099. 最小路径和 —— 动态规划入门详解

引言

动态规划的核心在于将复杂问题分解为重叠子问题，而「最小路径和」正是理解这一思想的经典范例。给定一个带权网格，每次只能向下或向右移动，求从左上到右下的最小路径和。这道题相比「粉刷房子」多了一个二维空间维度，但状态转移更加直观——每个格子的值只依赖于其上方和左方的格子。本文将带你从 DP 表格构造到代码实现，一步步掌握这道必刷题

摘要

本文详细解析力扣 LCR 099. 最小路径和的动态规划解法。给定 m×n 非负网格，每次只能向下或向右走，求左上到右下的最小路径和。定义 dp[i][j] 为到达 (i,j) 的最小路径和，转移方程 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])（上格子/左格子，二者取较小值）。重点讲解初始化边界：第一行只能从左边来，第一列只能从上边来，需先填好第一行、第一列这种边界值，然后再开始动态规划。提供二维数组和 O(n) 空间优化两种代码，时间复杂度 O(m×n)

目录

一、题目描述

二、动态规划思路

1. 为什么用 DP？

2. DP 数组的定义

3. DP 数组的构造（以示例 1 为例）

第一步：初始化 dp 数组

第二步：从 (1,1) 开始递推（双层循环）

4. 状态转移方程

三、Java 代码实现

四、代码优化（空间压缩）

五、易错点总结（特别重要）

⚠️ 注意点 1：初始化边界不能忘

⚠️ 注意点 2：理清"上一步来自哪里"

⚠️ 注意点 3：空间优化时一维数组的含义

六、复杂度分析

总结

一、题目描述

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

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

示例 1：

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

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 200

• 0 <= grid[i][j] <= 200

二、动态规划思路

1. 为什么用 DP？

到达 (i,j) 的最小路径和，只依赖于到达上方 (i-1,j) 和左方 (i,j-1) 的最小路径和。因为每次只能向下或向右，所以 (i,j) 的上一步只能是上面或左面——这就是最优子结构，适合用 DP 自顶向下推导。

2. DP 数组的定义

dp[i][j]：从左上角 (0,0) 走到 (i,j) 的最小路径和。

3. DP 数组的构造（以示例 1 为例）

输入：

grid = [[1,3,1],
[1,5,1],
[4,2,1]]

第一步：初始化 dp 数组

① 起点：

dp[0][0] = grid[0][0] = 1

② 初始化第一行（只能从左边来）：

dp[0][j] = dp[0][j-1] + grid[0][j]

即：

• dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4

• dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5

③ 初始化第一列（只能从上边来）：

dp[i][0] = dp[i-1][0] + grid[i][0]

即：

• dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2

• dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6

初始化完成后，dp 数组为：

第二步：从 (1,1) 开始递推（双层循环）

对于非边界格子 (i,j)，其值 = grid[i][j] + min(dp[i-1][j], dp[i][j-1])：

• dp[1][1] = 5 + min(dp[0][1]=4, dp[1][0]=2) = 5 + 2 = 7

• dp[1][2] = 1 + min(dp[0][2]=5, dp[1][1]=7) = 1 + 5 = 6

• dp[2][1] = 2 + min(dp[1][1]=7, dp[2][0]=6) = 2 + 6 = 8

• dp[2][2] = 1 + min(dp[1][2]=6, dp[2][1]=8) = 1 + 6 = 7

完整 dp 数组：

最终答案：dp[2][2] = 7 

4. 状态转移方程

边界情况：

• dp[0][0] = grid[0][0]

• 第一行：dp[0][j] = dp[0][j-1] + grid[0][j]（只能从左边来）

• 第一列：dp[i][0] = dp[i-1][0] + grid[i][0]（只能从上边来）

通用情况：

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

三、Java 代码实现

class Solution {
public int minPathSum(int[][] grid) {
//1.获取矩阵的行数和列数
int row = grid.length;
int col = grid[0].length;

//2.创建dp数组
int[][] dp = new int[row][col];

//3.初始化dp数组（初始化边界值：第一行、第一列）
//初始化左上角元素
dp[0][0] = grid[0][0];
//初始化第一列
for (int i = 1; i < row; i++) {

dp[i][0] = dp[i – 1][0] + grid[i][0];
}
//初始化第一行
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j – 1] + grid[0][j];
}

//4.开始动态规划的核心代码（填充dp数组）
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
//到达当前节点的最小路径 = 当前格子的耗费路径 + min(到达左面相邻格子的最小路径， 到达上面相邻格子的最小路径)
dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]);
}
}

//返回结果
return dp[row-1][col-1];
}
}

运行结果：

四、代码优化（空间压缩）

因为 dp[i][j] 只依赖于当前行的左方和上一行的同列，所以可以用一维数组滚动更新，空间复杂度降至 O(n)：

public static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;

int[] dp = new int[n];

// 初始化第一行
dp[0] = grid[0][0];
for (int j = 1; j < n; j++) {
dp[j] = dp[j-1] + grid[0][j];
}

// 从第二行开始
for (int i = 1; i < m; i++) {
dp[0] += grid[i][0]; // 第一列只能从上边来
for (int j = 1; j < n; j++) {
dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
// dp[j]（旧值）代表上方，dp[j-1]（新值）代表左方
}
}

return dp[n-1];
}

五、易错点总结（特别重要）

⚠️ 注意点 1：初始化边界不能忘

很多同学直接写双层循环，导致 i=0 或 j=0 时 dp[i-1][j] 或 dp[i][j-1] 越界。

正确做法： 先单独初始化第一行和第一列，再从 (1,1) 开始循环。

⚠️ 注意点 2：理清"上一步来自哪里"

因为只能向下或向右走，所以到达 (i,j) 的上一步只能是上方 (i-1,j) 或左方 (i,j-1)，不是四个方向，也不是斜对角。

⚠️ 注意点 3：空间优化时一维数组的含义

滚动数组版本中：

• dp[j] 在更新前代表上一行 (i-1,j) 的值

• dp[j-1] 已经更新为当前行 (i,j-1) 的值

所以 Math.min(dp[j], dp[j-1]) 正好对应 min(dp[i-1][j], dp[i][j-1])，不要搞反顺序。

六、复杂度分析

总结

这道题是动态规划中路径类问题的入门经典，核心思想是：

相比「粉刷房子」，本题的 DP 表格多了一个空间维度，但转移关系更加直观——"上一步来自哪里"一目了然。掌握这道题后，可以继续挑战「不同路径」「三角形最小路径和」等同类问题。

希望这篇文章能帮助你更好地理解动态规划！如果有问题，欢迎留言讨论 ！