800+ IT
News
als RSS Feed abonnieren📚 DP with Simple Matrix Traversal
💡 Newskategorie: Programmierung
🔗 Quelle: dev.to
64. Minimum Path Sum
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 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: `Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
1. Bottom-Up Recursive without memoization: TLE
We start building our solution from lowest values of row and col in a bottom-up fashion.
State Transition Equation
dp(i, j) = grid[i][j] + Min(dp(i+1, j), dp(i, j+1))
- 0 >= row <= m-1
- 0 >= col <= n-1
lowest values of row and col: 0
max values of row and col: m-1 & n-1
base case : When we are left with only 1 row and 1 col, min cost to reach to this cell from this cell is cost of this cell only.
`Java
class Solution {
int m;
int n;
int[][] grid;
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
this.m = m;
this.n = n;
this.grid = grid;
return dp(0, 0);
}
private int dp(int row, int col){
System.out.println("["+row+"]["+col+"]");
if(row == m-1 && col == n-1){
return grid[row][col];
}
if(!isValid(row, col)){
return Integer.MAX_VALUE;
}
return grid[row][col] + Math.min(dp(row+1, col), dp(row, col+1));
}
private boolean isValid(int row, int col){
return row >= 0 && col >= 0 && row <= m-1 && col <= n-1;
}
}
`
2. Bottom-Up Recursive with memoization: Accepted
`java
class Solution {
int m;
int n;
int[][] grid;
Integer[][] memo;
//dp(i, j) = grid[i][j] + Min(dp(i+1, j), dp(i, j+1));
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
this.m = m;
this.n = n;
this.grid = grid;
memo = new Integer[m+1][n+1];
return dp(0, 0);
}
private int dp(int row, int col){
System.out.println("["+row+"]["+col+"]");
if(row == m-1 && col == n-1){
return grid[row][col];
}
if(!isValid(row, col)){
return Integer.MAX_VALUE;
}
if(memo[row][col] != null){
return memo[row][col];
}
memo[row][col] = grid[row][col] + Math.min(dp(row+1, col), dp(row, col+1));
return memo[row][col];
}
private boolean isValid(int row, int col){
return row >= 0 && col >= 0 && row <= m-1 && col <= n-1;
}
}
`
3. Top-Down Recurisve with memoization: Accepted
We start building our solution from largest values of row and col in a top-down fashion
State Transition Equation
dp(i, j) = grid[i][j] + Min(dp(i-1, j), dp(i, j-1))
`
class Solution {
int m;
int n;
int[][] grid;
Integer[][] memo;
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
this.m = m;
this.n = n;
this.grid = grid;
memo = new Integer[m + 1][n + 1];
return dp(m - 1, n - 1);
}
private int dp(int row, int col) {
if (row == 0 && col == 0) {
return grid[row][col];
}
if (!isValid(row, col)) {
return Integer.MAX_VALUE;
}
if (memo[row][col] != null) {
return memo[row][col];
}
memo[row][col] = grid[row][col] + Math.min(dp(row - 1, col), dp(row, col - 1));
return memo[row][col];
}
private boolean isValid(int row, int col) {
return row >= 0 && col >= 0 && row <= m - 1 && col <= n - 1;
}
}
`
4. Bottom-Up Iterative with Memoization: Accepted
`
class Solution {
int m;
int n;
int[][] grid;
Integer[][] memo;
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
this.m = m;
this.n = n;
this.grid = grid;
memo = new Integer[m][n];
memo[m - 1][n - 1] = grid[m - 1][n - 1];
dp(m - 1, n - 1);
return memo[0][0];
}
private void dp(int row, int col) {
for (int i = row; i >= 0; i--) {
for (int j = col; j >= 0; j--) {
if(i == m-1 && j == n-1) continue; // last cell is already processed
int rightVal = isValid(i, j + 1) ? memo[i][j + 1] : Integer.MAX_VALUE;
int downVal = isValid(i + 1, j) ? memo[i + 1][j] : Integer.MAX_VALUE;
memo[i][j] = grid[i][j] + Math.min(rightVal, downVal);
}
}
}
private boolean isValid(int row, int col) {
return row >= 0 && col >= 0 && row <= m - 1 && col <= n - 1;
}
}
`
`
class Solution {
int count;
int m;
int n;
int[][] DP;
int[][] GRID;
int ans = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
this.m = grid.length;
this.n = grid[0].length;
this.count = 0;
this.GRID = new int[this.m][this.n];
this.DP = new int[this.m][this.n];
for (int i = 0; i < this.m; i++) {
System.arraycopy(grid[i], 0, GRID[i], 0, this.n);
}
// Fill all Dp with Int max
Arrays.stream(DP)
.parallel()
.forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
DP[m-1][n-1] = grid[m-1][n-1];
visit(0,0);
return DP[0][0];
}
private int visit(int r, int c) {
if (!isValidCell(r, c)) {
return Integer.MAX_VALUE;
}
// If already solved
if(DP[r][c] != Integer.MAX_VALUE){
return DP[r][c];
}
if ((r == (m - 1) && c == (n - 1))) {
return DP[r][c];
}
// 1. Analyze maximum sum of a path in worst case
// for a 200 x 200 grid where each cell has 200 and for the longest path
// max-sum= 200 * 200 * 200 = 8000000 << Int max(2147483647)
// 2. We can never get both down and right sum as Int max simultaneously.
// Its only possible for bottom right cell and for we are returning a predifned value.
DP[r][c] = GRID[r][c] + Math.min(visit(r + 1, c), visit(r, c+1));
return DP[r][c];
}
private boolean isValidCell(final int r, final int c) {
return r >= 0 && r < m && c >= 0 && c < n;
}
}
`