Java solution dp (somehow 3ms)


  • 0
    J
    public int minPathSum(int[][] grid) {
            int xSize = grid.length;
            int ySize = grid[0].length;
            if(xSize == 0)
                return 0;
            int[][] cache = new int[xSize][ySize];
            for (int i = 1; i < xSize; i++){
                for (int j = 1; j < ySize; j++){
                    cache[i][j] = Integer.MAX_VALUE;
                }
            }
            cache[0][0] = grid[0][0];
            for(int i = 1; i < ySize; i++){
                cache[0][i] = cache[0][i-1] + grid[0][i];
            }
            for(int i = 1; i < xSize; i++){
                cache[i][0] = cache[i-1][0] + grid[i][0];
            }
            for(int i = 1; i < xSize; i++){
                for(int j = 1; j < ySize; j++){
                    cache[i][j] = Math.min(cache[i-1][j], cache[i][j-1]) + grid[i][j];
                }
            }
            return cache[xSize-1][ySize-1];
        }

Log in to reply
 

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