个人网页设计概述_广州产品网站设计_网络营销买什么好_下载安装百度

和上一题几乎一模一样，只不过多了要比较的部分。

先用不节省空间的做法做了下：

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

试着降了下空间复杂度：

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