LeetCode 64. 最小路径和(HOT100)

第一次错误代码： 

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

正确代码：
 

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.size()==0)return 0;
        int m = grid.size(),n = grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,INT_MAX));
        dp[0][0]  = grid[0][0];
        //第一行
        for(int j = 1;j<n;j++){
            dp[0][j] = dp[0][j-1]+grid[0][j];
        }
        //第一列
        for(int j = 1;j<m;j++){
            dp[j][0] = dp[j-1][0]+grid[j][0];
        }
        //others
        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];        
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (!grid.size())
            return 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!i && !j) {//[0][0]
                    dp[0][0] = grid[0][0];
                } else if (!i) {//第一行
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (!j) {//第二行
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

空间优化：直接在grid数组上记录：

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

本题注意：第一列和第一行需要特殊处理，以为它们只能分别从上面 左边过来。