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];
}

3 comments:

  1. this is really very useful code . I used it in my prject it helped me alot
    Check JOB News updates

    ReplyDelete
  2. Catch the verb Stocktwits Live Real Time Stock Market Overview, your one stop shop for verb Stocktwits information. Live prices are updated every 5 minutes, so you see all of the latest verb Stocktwits changes as soon as they happen. With a sleek and intuitive user interface, we strive to make your data experience easy.

    ReplyDelete
  3. White Label Forex Meaning will enable you to get all the benefits of the MetaTrader 4 automated trading platform and MetaQuotes language with even more exciting functionalities for your own brand

    ReplyDelete

Blogroll

Popular Posts