3ms Java DP solution with recursive calls


  • 0
    R
    public class Solution {
        public int minPathSum(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
            int[][] pathLengths = new int[row][col];
            for (int i = 0; i < row; i++) Arrays.fill(pathLengths[i], -1);
            pathLengths[0][0] = grid[0][0];
            
            return helper(grid, pathLengths, row, col);
        }
    
        /**
         * select from the shorter path from the two previous squares of right-down corner square.
         *
         * don't foregt to store what has been calculated
         * */
    
        int helper(int[][] grid, int[][] pathLengths, int row, int col) {
            int pathLength = 0;
            if (row == 1) {
                for (int i = 1; i < col; i++) pathLengths[0][i] = pathLengths[0][i - 1] + grid[0][i];
                return pathLengths[0][col - 1];
            } else if (col == 1) {
                for (int i = 1; i < row; i++) pathLengths[i][0] = pathLengths[i - 1][0] + grid[i][0];
                return pathLengths[row - 1][0];
            } else {
                if (pathLengths[row - 1][col - 2] < 0) pathLengths[row - 1][col - 2] = helper(grid, pathLengths, row, col - 1);
                if (pathLengths[row - 2][col - 1] < 0) pathLengths[row - 2][col - 1] = helper(grid, pathLengths, row - 1, col);
                pathLengths[row - 1][col - 1] = grid[row - 1][col - 1] + Math.min(pathLengths[row - 1][col - 2],  pathLengths[row - 2][col - 1]);
                return pathLengths[row - 1][col - 1];
            }
        }
    }
    

Log in to reply
 

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