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