-
Notifications
You must be signed in to change notification settings - Fork 2
/
MinimumPathSum.java
76 lines (66 loc) · 1.76 KB
/
MinimumPathSum.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package com.algorithm.playground.leetcode.problems.lc0.lc64;
import java.util.Arrays;
/**
* https://leetcode.com/problems/minimum-path-sum/
*/
public class MinimumPathSum {
public class Solution {
public int minPathSum(int[][] grid) {
int i = 0, j = 0;
for (int c = 0; c < grid.length + grid[0].length - 1; c++) {
fillDiagonal(i, j, grid);
if (i < grid.length - 1) {
i++;
} else if (j < grid[0].length - 1) {
j++;
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
private void fillDiagonal(int i, int j, int[][] grid) {
while (i >= 0 && j < grid[0].length) {
if (i != 0 && j != 0) {
grid[i][j] = grid[i][j] + Math.min(grid[i - 1][j], grid[i][j - 1]);
} else if (i == 0 && j != 0) {
grid[i][j] = grid[i][j] + grid[i][j - 1];
} else if (i != 0) {
grid[i][j] = grid[i][j] + grid[i - 1][j];
}
i--;
j++;
}
}
}
class SolutionDFS {
private final int[] dr = new int[]{1, 0};
private final int[] dc = new int[]{0, 1};
public int minPathSum(int[][] grid) {
if (grid.length == 0) {
return 0;
}
int[][] cache = new int[grid.length][grid[0].length];
for (int[] row : cache) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dfs(0, 0, cache, grid, grid[0][0]);
return cache[grid.length - 1][grid[0].length - 1];
}
private void dfs(int r, int c, int[][] cache, int[][] grid, int sum) {
if (sum >= cache[r][c]) {
return;
}
cache[r][c] = sum;
if (r == grid.length - 1 && c == grid[0].length - 1) {
return;
}
int n = grid.length;
int m = grid[0].length;
for (int i = 0; i < 2; i++) {
int tr = r + dr[i], tc = c + dc[i];
if (tr >= 0 && tr < n && tc >= 0 && tc < m) {
dfs(tr, tc, cache, grid, sum + grid[tr][tc]);
}
}
}
}
}