Simple JAVA solution - DFS approach - O(m*n) space complexity


  • 0
    R
    public class Solution {
        int [][] dp;
        public int minPathSum(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            dp = new int[row][col];
            for (int i =0; i< row; i++) {
                Arrays.fill(dp[i],-1);
            }
            return minPathSumUtil(grid,0,0,row-1,col-1);
        }
        private int minPathSumUtil(int[][] grid, int i, int j, int row, int col) {
            if(i==row && j == col) return grid[i][j];
            if(i>row || j>col) return Integer.MAX_VALUE;
            else if (dp[i][j]!=-1) return dp[i][j];
            //traverse and take min cost
            dp[i][j] = Math.min(minPathSumUtil(grid, i, j+1, row, col),minPathSumUtil(grid, i+1, j, row, col))+grid[i][j];
            return dp[i][j];
        }
    }
    

Log in to reply
 

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