LeetCode 64 - Minimum Path Sum

作者 QIFAN 日期 2017-01-05
LeetCode 64 - Minimum Path Sum

原题链接: 64. Minimum Path Sum


题干

给定 m * n 的非负矩阵,求从左上角到右下角所有路径的最小和。只能往下或往右走。

思路

与这两题思路类似。
LeetCode 62 - Unique Paths
LeetCode 63 - Unique Paths

核心等式为:
sum(i, j) = min(sum(i - 1, j), sum(i, j - 1)) + nums[i][j]

我稍微变聪明点,直接先遍历第一列,然后往后算就好了,并且不新建数组,扣一点用原来给的那个。

时间复杂度 $O(MN)$ ,空间复杂度 $O(1)$ 。

public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (col == 0 && row == 0) {
continue;
}
if (col == 0) {
grid[row][col] += grid[row - 1][col];
} else if (row == 0) {
grid[row][col] += grid[row][col - 1];
} else {
grid[row][col] += Math.min(grid[row - 1][col], grid[row][col - 1]);
}
}
}
return grid[grid.length - 1][grid[0].length - 1];
}