Thursday, January 1, 2015

Minimum Path Sum (LeetCode Array)

Question: 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.
Note: You can only move either down or right at any point in time.

Idea: Dynamic programming. Assume the F[i][j] is the minimum path sum from (i,j) to (m-1, n-1). Then we have the equation:
F[i][j]=grid[i][j]+Math.min(F[i+1][j], F[i][j+1]). The result is F[0][0].

Time: O(n^2) Space: O(n^2)

Code:
 public class Solution{  
      public int minPathSum(int[][] grid) {  
           if(grid.length==0||grid[0].length==0)  
                return 0;  
           int[][] path=new int[grid.length][grid[0].length];  
           int m=grid.length;  
           int n=grid[0].length;  
           path[m-1][n-1]=grid[m-1][n-1];  
           for(int j=n-2;j>=0;j--)  
                path[m-1][j]=grid[m-1][j]+path[m-1][j+1];  
           for(int i=m-2;i>=0;i--)  
                path[i][n-1]=grid[i][n-1]+path[i+1][n-1];  
           for(int i=m-2;i>=0;i--)  
           {  
                for(int j=n-2;j>=0;j--)  
                {  
                     path[i][j]=grid[i][j]+Math.min(path[i+1][j],path[i][j+1]);  
                }  
           }  
           return path[0][0];  
   }  
 }  

No comments:

Post a Comment