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];}//othersfor(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];}
};

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