怎么修改网页上的内容_黄冈如何创建免费网站_南通百度网站快速优化_市场营销模式有哪些

题目：

解答：

简单dp。

定义：dp[i][j]为到达(i,j)所需要的最短路程

初始化：dp[0][0]=grid[0][0]，同时对第一行和第一列的，第i个就是前i个之和加上自身

递归：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j],也就是从上面到达或者从左边到达

空间复杂度O(mn),m为grid行数，n为grid列数，作空间优化

vector<vector<int>> dp(m,vector<int>(2)) m行2列的vector 降低空间复杂度为m（这里也可以先写个if，判断m和n大小，来决定是m行2列还是m列2行，不影响时间复杂度）

按照一列一列来遍历，修改初始化条件，先初始化第一列，然后从第二列开始，dp[0][1]单独计算，dp[j][1]按照上述递归式子的算法计算。一列遍历完成后，用dp[m][0]=dp[m][1]来存储状态，继续扫描下一列。最后return dp[m-1][1]即可

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

时间复杂度O(mn)

空间复杂度O(m)