Wednesday, October 16, 2013

Minimum Path Sum [Leetcode]

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: compute the minimum path sum for each element grid (i, j)  from top left row by row.

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(grid.empty() || grid[0].empty()) return 0;

        int x = grid.size(), y=grid[0].size();
        for(int i=0; i<x; i++)
            for(int j=0; j<y; j++){
                if(i==0)
                    grid[i][j] += (j==0?0:grid[i][j-1]);
                else
                    grid[i][j] += min(grid[i-1][j], (j==0?INT_MAX:grid[i][j-1]));
            }
        return grid.back().back();
    }
};

No comments:

Post a Comment