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];

    }    

};