Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

JavaScript Code

function minPathSum(grid) {
    if(grid == null || grid.length==0)
        return 0;
 
    var m = grid.length;
    var n = grid[0].length;
 
    var dp = [];
    for(var i=0;i<m;i++) {
        var temp = [];
        for(var j=0;j<n;j++) {
            temp.push(0);
        }   
        dp.push(temp);
    }
    dp[0][0] = grid[0][0];
    
    // initialize top row
    for(var i=1; i<n; i++){
        dp[0][i] = dp[0][i-1] + grid[0][i];
    }
    
    // initialize left column
    for(var j=1; j<m; j++){
        dp[j][0] = dp[j-1][0] + grid[j][0];
    }
    
    // fill up the dp table
    for(var i=1; i<m; i++){
        for(var j=1; j<n; j++){
            if(dp[i-1][j] > dp[i][j-1]){
                dp[i][j] = dp[i][j-1] + grid[i][j];
            }else{
                dp[i][j] = dp[i-1][j] + grid[i][j];
            }
        }
    }
    
    return dp[m-1][n-1];
}

0 comments:

Blogroll

Follow this blog by Email

Popular Posts