leetcode-java/src/MinimumPathSum64.java at master · fluency03/leetcode-java · GitHub

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
 * Given a m x n grid filled with non-negative numbers, find a path from top
 * left to bottom right which minimizes the sum of all numbers along its path.
 *
 * Note: You can only move either down or right at any point in time.
 */


publicclassMinimumPathSum64 {
publicintminPathSum(int[][] grid) {
intm = grid.length;
intn = grid[0].length;
int[][] dp = newint[m][n];

for (inti = 0; i < m; i++)
for (intj = 0; j < n; j++)
dp[i][j] = Integer.MAX_VALUE;

dp[0][0] = grid[0][0];
for (inti = 1; i < m; i++)
dp[i][0] = grid[i][0] + dp[i - 1][0];
for (inti = 1; i < n; i++)
dp[0][i] = grid[0][i] + dp[0][i - 1];

for (inti = 0; i < m; i++) {
for (intj = 0; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
 }
 }

returndp[m-1][n-1];
 }


/**
 * https://discuss.leetcode.com/topic/22732/my-solution-beats-100-java-solutions
 */
publicintminPathSum1(int[][] grid) {
if(grid.length == 0) return0;

intr = grid.length;
intc = grid[0].length;

for(inti=0;i<r; i++) {
for(intj=0; j<c; j++) {
intleftSum = (j>0) ? grid[i][j-1] : Integer.MAX_VALUE;
inttopSum = (i>0) ? grid[i-1][j] : Integer.MAX_VALUE;
if(i==0 && j==0) continue;

grid[i][j] += Math.min(leftSum, topSum);
 }
 }
returngrid[r-1][c-1];
 }


/**
 * https://discuss.leetcode.com/topic/38213/my-java-solution-using-dp-with-memorization-beats-about-98-submissions
 */
publicintminPathSum2(int[][] grid) {
int[][] memo = newint[grid.length][grid[0].length];
returnminPathSumHelper(grid, 0, 0, memo);
 }

publicintminPathSumHelper(int[][] grid, introw, intcol, int[][] memo) {
if(row == grid.length-1 && col == grid[0].length-1) returngrid[row][col];
if(memo[row][col] != 0) returnmemo[row][col];

introwInc = Integer.MAX_VALUE, colInc = Integer.MAX_VALUE;
if(row < grid.length-1) rowInc = minPathSumHelper(grid, row+1, col, memo);
if(col < grid[0].length-1) colInc = minPathSumHelper(grid, row, col+1, memo);
memo[row][col] = Math.min(rowInc, colInc) + grid[row][col];
returnmemo[row][col];
 }


/**
 * https://discuss.leetcode.com/topic/85826/java-solution-1ms-recursive-and-4ms-iterative
 */
publicintminPathSum3(int[][] grid) {
int[][] dp = newint[grid.length][grid[0].length];
returnminPathSum(grid, 0, 0, dp);
 }

publicintminPathSum(int[][] grid, inti, intj, int[][] dp) {
if (i == grid.length || j == grid[0].length) {
returnInteger.MAX_VALUE;
 }
if (i == grid.length - 1 && j == grid[0].length - 1) {
returngrid[i][j];
 }
if (dp[i][j] != 0) {
returndp[i][j];
 }

intmin = grid[i][j];
min += Math.min(minPathSum(grid, i, j + 1, dp), minPathSum(grid, i + 1, j, dp));
dp[i][j] = min;
returnmin;
 }


publicintminPathSum4(int[][] grid) {
intM = grid.length;
if (M == 0) return0;
intN = grid[0].length;
if (N == 0) return0;
for (intj=1; j<N; j++) grid[0][j] += grid[0][j-1];
for (inti=1; i<M; i++) grid[i][0] += grid[i-1][0];
for (inti=1; i<M; i++) {
for (intj=1; j<N; j++) {
grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
 }
 }
returngrid[M-1][N-1];
 }

}