Page 10

DFS brute force

T: O(2^mn)

DFS + memo

T: O(mn)

S: O(mn)

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        return dfs(grid, 0, 0, new Integer[m][n]);
        
    }
    private int dfs(int[][] grid, int row, int col, Integer[][] memo) {
        int m = grid.length;
        int n = grid[0].length;
        

        if (row == m-1 && col == n-1) { // base case
            return grid[row][col];
        }
        if (row >= m || col >= n) { // exception
            return Integer.MAX_VALUE;
        }
        
        if (memo[row][col] != null) { // memo
            return memo[row][col];
        }
        
        int result = grid[row][col] + Math.min(dfs(grid, row+1, col, memo), dfs(grid, row, col+1, memo));
        return memo[row][col] = result;
        
    }
}
/*
You can only move either down or right at any point in time.
*/