64. 最小路径和
查看题目中等
算法
低频
解法一：动态规划
时间复杂度：O(m*n) | 空间复杂度：O(m*n) | 推荐使用
动画演示
准备就绪 - 输入网格值（用分号分隔行，逗号分隔列），然后点击开始
代码实现
class Solution {
/**
* 计算从左上角到右下角的最小路径和
* @param grid 包含非负整数的二维网格
* @return 最小路径和
*/
public int minPathSum(int[][] grid) {
// 边界条件检查
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length; // 网格行数
int columns = grid[0].length; // 网格列数
int[][] dp = new int[rows][columns]; // dp数组，存储到每个位置的最小路径和
// 初始化起点
dp[0][0] = grid[0][0];
// 初始化第一列
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 初始化第一行
for (int j = 1; j < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 填充其他位置
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
// 选择从左边或上边来的较小路径和
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
// 返回右下角的最小路径和
return dp[rows - 1][columns - 1];
}
}
时间复杂度：O(m*n)
空间复杂度：O(m*n)
我们使用动态规划来解决这个问题。
1. 首先创建一个二维数组 dp，其中 dp[i][j] 表示从左上角到 (i,j) 位置的最小路径和。
2. 初始化边界条件：
- 第一行的每个位置只能从左边过来，所以 dp[0][j] = dp[0][j-1] + grid[0][j]
- 第一列的每个位置只能从上边过来，所以 dp[i][0] = dp[i-1][0] + grid[i][0]
3. 对于其他位置 (i,j)，可以从左边或上边过来，选择其中较小的路径和：
- dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
4. 最终，dp[m-1][n-1] 就是从左上角到右下角的最小路径和。
这种方法的时间复杂度是 O(m*n)，空间复杂度也是 O(m*n)，其中 m 和 n 分别是网格的行数和列数。