[数据结构与算法]64.最小路径和

解题思路：

一 深度优先搜索，这种方法需要遍历所有的路径，复杂度较高。

二 动态规划

1 创建一个大小和矩阵一样大小的二位数组dp，来记录走到当前位置的最小路径和。

2 因为只能向下或向右走，所以当行号索引或列号索引等于0时，需要单独考虑，只要加上把当前位置的值加上前一个dp的值就可以。

3 其他情况需要用到动态转移方程dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);

4返回dp右下角的值就可以了

class Solution {
public:

    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();

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

        //dp表示从(i,j)点走到(m-1,n-1)点的最小路径和
        vector<vector<int>>dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];

        for(int i=1;i<m;++i){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }

        for(int i=1;i<n;++i){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
      
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
               dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];
  
    }
};