Leetcode
Dynamic Programming
64 Minimum Path Sum

1. Question

Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
Note:You can only move either down or right at any point in time.
Example 1:
1
[[1,3,1],
2
[1,5,1],
3
[4,2,1]]
Copied!
Given the above grid map, return7. Because the path 1→3→1→1→1 minimizes the sum.

2. Implementation

(1) DP
1
class Solution {
2
public int minPathSum(int[][] grid) {
3
if (grid == null || grid.length == 0) {
4
return 0;
5
}
6
7
int m = grid.length, n = grid[0].length;
8
int[][] dp = new int[m][n];
9
dp[0][0] = grid[0][0];
10
11
for (int i = 1; i < m; i++) {
12
dp[i][0] = dp[i - 1][0] + grid[i][0];
13
}
14
15
for (int j = 1; j < n; j++) {
16
dp[0][j] = dp[0][j - 1] + grid[0][j];
17
}
18
19
for (int i = 1; i < m; i++) {
20
for (int j = 1; j < n; j++) {
21
dp[i][j] = grid[i][j] + Math.min(dp[i][j - 1], dp[i - 1][j]);
22
}
23
}
24
return dp[m - 1][n - 1];
25
}
26
}
Copied!

3. Time & Space Complexity

时间复杂度O(mn), 空间复杂度O(mn)