Saturday, May 10, 2014

Minimum Path Sum

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.

Solution : 

This can be done by in place dynamic programming. The idea is to replace matrix[i][j] values with the minimum value that can be achieved (among two paths) to reach matrix[i][j].
We can reach matrix[i][j] through one of 
matrix[i-1][j] or
matrix[i][j-1]
We record the minimum of these two at matrix[i][j].

Code:
class Solution {
public:
    int minPathSum(vector > &grid) {

    int i,j;
     for(i=0;i
        for(j=0;j
        {
           if(!(i==0 && j==0))
            {
                if(i==0 && j>0)
                  grid[i][j] += grid[i][j-1];
              else  if(i> && j==0)
                 grid[i][j]  += grid[i-1][j];
               else
                 grid[i][j] += min(grid[i][j-1], grid[i-1][j]); 
             }
         }
         return grid[i][j];
}
};

No comments:

Post a Comment