64.最小路径

题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路
方法类同62和63，但是在求path[i][j]时需要加的时其本身和左上的最小值

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int sizeOf = grid.size(), lengthOf = grid[0].size();
        vector<vector<int>>path(sizeOf, vector<int>(lengthOf, 0));
        path[0][0] = grid[0][0];
        for (int i = 1; i < sizeOf; ++i)
        {
            path[i][0] = grid[i][0] + path[i - 1][0];
        }
        for (int i = 1; i < lengthOf; ++i)
        {
            path[0][i] = grid[0][i] + path[0][i - 1];
        }
        for (int i = 1; i < sizeOf; ++i)
            for (int j = 1; j < lengthOf; ++j)
            {
                path[i][j] = grid[i][j] + min(path[i - 1][j], path[i][j - 1]);
            }
        return path[sizeOf - 1][lengthOf - 1] ;
    }
};

int main(int argc, char* argv[])
{
    vector<vector<int>> test = { { 1,3,1 },{ 1,5,1 },{ 4,2,1 } };
    auto res = Solution().minPathSum(test);
    return 0;
}