LeetCode064——最小路径和
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/minimum-path-sum/description/
题目描述:
知识点:动态规划
思路:动态规划
本题的思路和LeetCode062——不同路径与LeetCode063——不同路径II一模一样。
状态定义:f(x, y) -------- 到达坐标(x, y)的最小路径和
状态转移:
(1)如果x == 0,到达坐标(0, y)的最小路径和就是grid数组中坐标从(0, 0)到(0, y)的累加和。
(2)如果y == 0,到达坐标(x, 0)的最小路径和就是grid数组中坐标从(0, 0)到(x, 0)的累加和。
(3)否则,f(x, y) = min{f(x - 1, y), f(x, y - 1)} + grid[x, y]。
时间复杂度和空间复杂度均为O(m * n),其中m为grid的行数,n为grid的列数。
JAVA代码:
public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
if(m == 0) {
return 0;
}
int n = grid[0].length;
int[][] map = new int[m][n];
map[0][0] = grid[0][0];
for (int i = 1; i < n; i++) {
map[0][i] = map[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
map[i][0] = map[i - 1][0] + grid[i][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
map[i][j] = Math.min(map[i - 1][j], map[i][j - 1]) + grid[i][j];
}
}
return map[m - 1][n - 1];
}
}
LeetCode解题报告: