1. 064

minimum-path-sum

2. 算法

DP:O(n^2)

• 递推关系，比如设存放起点到每个格子 i，j 的最小路径和的二维数组为 MPS[i][j]，那么递推公式为：

• MPS[i][j] = Min（MPS[i-1][j]，MPS[i][j-1]）+ val[i][j]；

• 即格子 i，j 的MPS值可能有两个来源：其左侧格子 i，j-1 或者其上侧格子 i-1，j ；取这两个来源的较小MPS值，再加上当前格子的值 val[i][j] 即为结果。

3. 代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.size()==0)
            return 0;
        vector<vector<int> > res(grid);
        int i,j;
        for(int j=1;j<res[0].size();++j)
            res[0][j]+=res[0][j-1];
        for(int j=1;j<res.size();++j)
            res[j][0]+=res[j-1][0]; 
        for(int i=1;i<res.size();++i)
            for(int j=1;j<res[i].size();++j)
                res[i][j]=min(res[i-1][j],res[i][j-1]+grid[i][j]);
        return res[grid.size()-1][grid[0].size()-1];
    }    
};