题解 | #矩阵的最小路径和#

using namespace std;

int DP(vector<vector<int>> &mat,vector<vector<int>>& dp,int x,int y){
    int n,m;
    n=mat.size();m=mat[0].size();
    if(!x&&!y)//左上角
        return dp[x][y];
    if(!x)//第一行
        return dp[x][y]+dp[x][y-1];
    if(!y)//第一列
        return dp[x][y]+dp[x-1][y];
    return dp[x][y]+min(dp[x-1][y],dp[x][y-1]);
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> matrix(n,vector<int>(m));
    vector<vector<int>> dp(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>matrix[i][j];
    for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
           dp[i][j]=matrix[i][j];
        
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            dp[i][j]=DP(matrix,dp,i,j);
        }
    cout<<dp[n-1][m-1];
    return 0;
}