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

  • 0
    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++) {
            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.