題目描述：給定一個二維數組matrix，一個人必須從左上角出發，最后到達右下角，沿途只可以向下或者向右走，沿途的數字都累加就是距離累加和，返回最小距離累加和。

way：無他，dp[i] [j]表示(i,j)坐標位置的最小距離和。

#include<iostream>
#include<vector>
using namespace std;int minPathSum(vector<vector<int>> matrix)
{int row=matrix.size();int col=matrix[0].size();vector<vector<int>>dp(row,vector<int>(col));dp[0][0]=matrix[0][0];//第一行的dp值只能從左邊過來for(int j=1; j<col; j++){dp[0][j]=dp[0][j-1]+matrix[0][j];}//第一列的dp值只能從上邊過來for(int i=1; i<row; i++){dp[i][0]=dp[i-1][0]+matrix[i][0];}//從第二行第二列及其后的dp值可以從左邊或上邊過來for(int i=1; i<row; i++){for(int j=1; j<col; j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+matrix[i][j];}}return dp[row-1][col-1];
}

way2：一層dp。

//改成一層dp
int minPathSum2(vector<vector<int>> matrix)
{int row=matrix.size();int col=matrix[0].size();vector<int>dp(col);//初始值dp[0]=matrix[0][0];//第一行的值for(int j=1; j<col; j++){dp[j]=dp[j-1]+matrix[0][j];}//從第二行及其往后的行的值for(int i=1; i<row; i++){//表示第一列的值只能從上面過來dp[0]+=matrix[i][0];for(int j=1; j<col; j++){//dp[j]是上一行的dp[j],dp[j-1]是這一行更新的最新的dp[j-1]dp[j]=min(dp[j],dp[j-1])+matrix[i][j];}}return dp[col-1];
}