64. 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.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

---

一个网格，每个格子中都有一个数字，问从左上角走到右下角，求走过的格子数字之和最小值是多少。 和LeetCode Unique Paths II是一样的，一个格子只可能从其左边或者上边的格子而来，所以求两者最小值即可。不过要注意边界问题，完整代码如下：

class Solution {
public:
    int minPathSum(vector<vector<int> >& grid)
    {
        vector<int> dp(grid[0].size(), 0);
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                int top = i == 0 ? INT_MAX : dp[j];
                int left = j == 0 ? INT_MAX : dp[j – 1];
                if (i == 0 && j == 0)
                    dp[j] = grid[i][j];
                else
                    dp[j] = (top < left ? top : left) + grid[i][j];
            }
        }
        return dp[grid[0].size() – 1];
    }
};

本代码提交AC，用时16MS。