problem：

thinking：

（1）矩阵的路径问题（求路径总数。带障碍物的路径总数。加权最小、最大路径等），因为具有清晰且简易的状态转移公式，

统统能够用DP法解决，时间复杂度都为O（m*n）

(2) 用DP解决全局最优问题！

。该题是否具有局部最优解呢。状态转移公式：a[i][j] = min(a[i-1][j], a[i][j-1]) + grid[i][j];

规定了每一步的选择都是最优解。所以局部最优是成立的

code：

class Solution {

public:

    int minPathSum(vector<vector<int> > &grid) {

        vector<vector<int> >::const_iterator con_it=grid.begin();

        int m=grid.size();

        int n=(*con_it).size();

        vector<int> tmp(n,0);

        vector<vector<int> > a(m,tmp);

        if(m==0 || n==0)

            return 0;

        a[0][0]=grid[0][0];

        for(int i=1;i<m;i++)

           a[i][0]=a[i-1][0]+grid[i][0];

        for(int j=1;j<n;j++)

            a[0][j]=a[0][j-1]+grid[0][j];

        for(int i = 1; i < m; i++)

            for(int j = 1; j < n; j++)

                a[i][j] = min(a[i-1][j], a[i][j-1]) + grid[i][j];

        return a[m-1][n-1];

    }

};