Elementary Java DP solution


  • 0
    L
    public class Solution {
    public int minPathSum(int[][] grid) {
        /**
         * dp[i][j] denoting the minimum sum from (0,0) to (i,j)
         * dp[0][j] = dp[0][j-1]+grid[0][j]
         * dp[i][0] = dp[i-1][0]+grid[i][0]
         * otherwise dp[i][j]= min(dp[i][j-1],dp[i-1][j])+dp[i][j]
         * */
        int row = grid.length;
        if(row == 0) return 0;
        int col = grid[0].length;
        if(col == 0) return 0;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];
        for(int i = 1;i<col;i++) dp[0][i] = dp[0][i-1]+grid[0][i];//populate first row
        for(int i = 1;i<row;i++) dp[i][0] = dp[i-1][0]+grid[i][0];//populate first col
        for(int i = 1;i<row;i++){
            for(int j =1;j<col;j++){
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
    

    }


Log in to reply
 

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