-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
64 lines (58 loc) · 2.12 KB
/
Solution.java
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
package minimumpathsum;
/**
* 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.
*
* Example:
*
* Input:
* [
* [1,3,1],
* [1,5,1],
* [4,2,1]
* ]
* Output: 7
* Explanation: Because the path 1→3→1→1→1 minimizes the sum.
*/
public class Solution {
int minPathSum_ApproachOne(int[][] grid) {
return calc(grid, 0,0);
}
/**
* Approach 1 - Brute Force, for each cell, check both forward & downward path
* TLE
*/
private int calc(int[][] grid, int i, int j) {
// if destination - return cell value
if(i == grid.length -1 && j == grid[i].length - 1) return grid[i][j];
// if i or j exceeds
if(i == grid.length || j == grid[0].length) return Integer.MAX_VALUE;
// else return sum of cell + min of right path & down path
return grid[i][j] + Math.min(calc(grid, i+1, j), calc(grid, i, j+1));
}
/**
* Approach 2 - DP, with another matrix for storing min path sums
* Runtime: 3 ms, faster than 24.25% of Java online submissions for Minimum Path Sum.
* Memory Usage: 42.1 MB, less than 85.13% of Java online submissions for Minimum Path Sum.
*
* Time - O(mn), Space - O(mn)
*/
// TODO: Study other solutions
int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
dp[i][j] = grid[i][j] + dp[i][j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
dp[i][j] = grid[i][j] + dp[i + 1][j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
else
dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
}