題目：

解答：

簡單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)