Leetcode 64: minimal 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.

这道题和之前的题目方法是类似的， 只是induction rule 有变化，并且边缘的induction rule 和中间的induction rule是不同的。 所以需要分别计算。
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //sanity check
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int M[grid[0].size()] = {0};
        M[0] = grid[0][0];
        //induction rule for the first row sum
        for (int i = 1; i < grid[0].size(); i++) {
            M[i] = grid[0][i] + M[i-1];
        }
        for (int i = 1; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (j > 0 ) M[j] = grid[i][j] + min (M[j], M[j-1]);
                else M[j] += grid[i][j];
            }
        }
        return M[grid[0].size()-1];
    }
};