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:
Post a comment