forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumPathSum.java
More file actions
81 lines (72 loc) · 1.85 KB
/
MinimumPathSum.java
File metadata and controls
81 lines (72 loc) · 1.85 KB
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
package DynamicProgramming;
/*
Given the following grid with length m and width n:
\---\---\---\ (n)
\ 1 \ 3 \ 1 \
\---\---\---\
\ 1 \ 5 \ 1 \
\---\---\---\
\ 4 \ 2 \ 1 \
\---\---\---\
(m)
Find the path where its sum is the smallest.
All numbers given are positive.
The Time Complexity of your algorithm should be smaller than or equal to O(mn).
The Space Complexity of your algorithm should be smaller than or equal to O(mn).
You can only move from the top left corner to the down right corner.
You can only move one step down or right.
EXAMPLE:
INPUT: grid = [[1,3,1],[1,5,1],[4,2,1]]
OUTPUT: 7
EXPLANATIONS: 1 + 3 + 1 + 1 + 1 = 7
For more information see https://www.geeksforgeeks.org/maximum-path-sum-matrix/
*/
public class MinimumPathSum {
public void testRegular() {
int[][] grid = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
System.out.println(minimumPathSum(grid));
}
public void testLessColumns() {
int[][] grid = {
{1, 2},
{5, 6},
{1, 1}
};
System.out.println(minimumPathSum(grid));
}
public void testLessRows() {
int[][] grid = {
{2, 3, 3},
{7, 2, 1}
};
System.out.println(minimumPathSum(grid));
}
public void testOneRowOneColumn() {
int[][] grid = {{2}};
System.out.println(minimumPathSum(grid));
}
public static int minimumPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
if (n == 0) {
return 0;
}
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 0; i < n - 1; i++) {
dp[0][i + 1] = dp[0][i] + grid[0][i + 1];
}
for (int i = 0; i < m - 1; i++) {
dp[i + 1][0] = dp[i][0] + grid[i + 1][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}