动态规划中等1 种解法
#64最小路径和
从网格左上角只向右或向下移动，求到右下角的最小路径数字和。
#数组#动态规划#矩阵
原题
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
解题主线
- 到达当前格的最小代价只可能来自上方或左方；第一行和第一列各只有一种路径。
解法 1：二维动态规划
初始化两条边界，再按行递推 dp[row][column]。
-
时间复杂度： O(mn)
-
空间复杂度： O(mn)
final class Solution {
public int minPathSum(int[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
// dp[row][column] 表示从左上角到当前格的最小路径和
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
// 第一列只能从上方到达，第一行只能从左侧到达
for (int row = 1; row < rows; row++) {
dp[row][0] = dp[row - 1][0] + grid[row][0];
}
for (int column = 1; column < columns; column++) {
dp[0][column] = dp[0][column - 1] + grid[0][column];
}
for (int row = 1; row < rows; row++) {
for (int column = 1; column < columns; column++) {
// 内部格选择上方与左方中代价更小的前驱
dp[row][column] = Math.min(dp[row - 1][column], dp[row][column - 1])
+ grid[row][column];
}
}
return dp[rows - 1][columns - 1];
}
}边界与易错点
- 第一行、第一列必须单独初始化。
- 若允许修改输入，可直接把 grid 作为 dp 表以降至 O(1) 额外空间。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q064_minPathSum.java