DP with Simple Matrix Traversal

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. Top-Down (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)) where,

• 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 (1x1 grid), min-cost to reach to this cell from this cell is grid[0][0] (cost of this cell only).

`
public 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) {
    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. Top-Down (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. Bottom-Up (with memoization) ...Accepted

NOTE:: not a common approach

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))

`java
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

`java
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;
}

}
`