I used DP, but I don't why it's so slow, only beats 5%. how to improve it? thanks


  • 0

    Hi friends
    I made a DP solution, but it's very slow that only beats 5%. how to improve it? thanks

        public int minPathSum(int[][] grid) {
            int rowCount = grid.length;
            int colCount = grid[0].length;
            int[][] result = new int[rowCount][colCount];
    
            for(int i = rowCount-1; i>=0; i--){
                for(int j = colCount-1; j >= 0; j--) {
                    if(i==rowCount-1 && j==colCount-1){
                        result[rowCount-1][colCount-1] = grid[rowCount-1][colCount-1];
                    } else {
                        result[i][j] = grid[i][j] + Math.min((i+1 < rowCount) ? result[i+1][j] : Integer.MAX_VALUE, 
                                                             (j+1 < colCount) ? result[i][j+1] : Integer.MAX_VALUE);
                    }
                }
            }
            
            return result[0][0];
        }
    
    

Log in to reply
 

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