Skip to content

add MinimumPathSum DynamicProgramming #2068

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Jan 4, 2021
Merged

add MinimumPathSum DynamicProgramming #2068

Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
71c57a9
add MinimumPathSum DynamicProgramming
Dec 23, 2020
9091c60
add tests and link for the algorithm
Dec 23, 2020
8230ce5
remove junit dependency
Dec 23, 2020
c3a3e13
format with google code format
Dec 23, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
81 changes: 81 additions & 0 deletions DynamicProgramming/MinimumPathSum.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,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];
}
}