DP with Simple Matrix Traversal
Published: 2024-05-11 21:22:02



### [64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/description/)

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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h2egdlzr3prn40kjtqvz.png)

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