4ms Java DP recursive DFS solution


  • 0
    T
    public class Solution {
    int [][] dpTable;
    public int minPathSum(int[][] grid) {
        int n = grid.length -1;
        int m = grid[0].length -1;
        dpTable = new int [grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++){
            for (int k = 0; k < grid[0].length; k++){
                dpTable[i][k] = -1;
            }
        }
        return minCost(grid, 0, 0, n, m); 
    }
    
    int minCost(int[][] grid, int rowNum, int colNum, int n, int m) {
        int costOfDown = 0;
        int costOfRight = 0;
        
        if(rowNum == n && colNum == m) {
            return grid[rowNum][colNum];
        }
        
        if(rowNum < n) {
            if (dpTable[rowNum+1][colNum] == -1) {
                costOfDown = minCost(grid, rowNum+1, colNum, n, m);
                dpTable[rowNum+1][colNum] = costOfDown;
            }
            else{
                costOfDown = dpTable[rowNum+1][colNum];
            }
        }
        else{
            costOfDown = 999999; // infinity
        }
        
        if(colNum < m) {
            if (dpTable[rowNum][colNum+1] == -1)
            {
                costOfRight = minCost(grid, rowNum, colNum+1, n, m);
                dpTable[rowNum][colNum+1] = costOfRight;
            }
            else{
                costOfRight = dpTable[rowNum][colNum+1];
            }
        }
        else {
            costOfRight = 999999; // infinity
        }
        
        return grid[rowNum][colNum] + ((costOfDown < costOfRight) ? costOfDown : costOfRight);
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.