GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Algorithms---Java/DynamicProgramming/MinimumPathSum.java at master · PrideIceMan/Algorithms---Java

Expand file tree

/

MinimumPathSum.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
81 lines (72 loc) · 1.85 KB
/

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];
}
}
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.