算法思想

与62,63题很相似，只需要维护一个一维数组，每次更新一维数组的值时进行运算dp[j]=min(dp[j-1],dp[j])+grid[i][j-1]即可，但是需要注意事先对边界值的处理

我的解法

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<int> dp(n+1,0);
        //dp[1]=grid[0][0]; 因为下续循环中i==0时会对此值进行重新的计算
        for(int i=0;i<m;i++)
            for (int j=1;j<=n;j++)
            {
                if(i==0)
                    dp[j]=dp[j-1]+grid[i][j-1];
                if(j==1 &&i!=0)    //最左边一列的边缘处理，i!=0是为了去除左上节点背运算两次
                    dp[j]=dp[j]+grid[i][j-1];
                else
                    dp[j]=min(dp[j-1],dp[j])+grid[i][j-1];
            }
        return dp.back();   
    }
};

最优解法

推荐的最快时间算法在空间复杂度上不足，与本解法的时间差在于对边界值处理时在一维循环里会快于二维循环，因此也可以对我的解法进行时间上的优化处理。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(); 
        if(m==0) return 0; 
        int n=grid[0].size(); 
        
        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 j=1; j<n; j++) dp[0][j]=dp[0][j-1]+grid[0][j]; 
        
        for(int i=1; i<m; i++)
            for(int j=1; j<n; j++){
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j]; 

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

    }
};