FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DynamicProgramming/MinimumPathSum.java at master · fernandor777/Java · GitHub
fernandor777
/
Java
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DynamicProgramming
/
MinimumPathSum.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
81 lines (72 loc) · 1.85 KB
Breadcrumbs
Java
/
DynamicProgramming
/
MinimumPathSum.java
Copy path
File metadata and controls
81 lines (72 loc) · 1.85 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
];
}
}
Back
|
FazBrowse Home
|
New Git URL