DP Java solution 3ms


  • 0
    S
        public int minPathSum(int[][] grid) {
            int[][] cache = new int[grid.length][grid[0].length];
            for (int[] row : cache) {
                Arrays.fill(row, -1);
            }
        return minPathSum(grid, grid.length - 1, grid[0].length - 1, cache);
        }
        
        public int minPathSum(int[][] grid, int m, int n, int[][] cache) {
            if (m == 0 && n == 0) {
                return grid[0][0];
            } else if (m == 0 && n != 0) {
                return grid[0][n] + minPathSum(grid, 0, n-1, cache);
            } else if (m != 0 && n == 0) {
                return grid[m][0] + minPathSum(grid, m-1, 0, cache);
            }
            
            if (cache[m][n] != -1 ) {
                return cache[m][n];
            } else {
                if (minPathSum(grid, m-1, n, cache) < minPathSum(grid, m, n-1, cache)) {
                    cache[m][n] = grid[m][n] + minPathSum(grid,m-1,n,cache);
                } else {
                    cache[m][n] = grid[m][n] + minPathSum(grid,m,n-1,cache);
                }
                return cache[m][n];
            }
            
            
        }
    }```

Log in to reply
 

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