题解 | 矩阵的最小路径和

 #include <iostream>
 using namespace std;
 #include <vector>
 int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>s(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    vector<int>dp(m+1,0);
    dp[1]=s[1][1];
    for(int j=2;j<=m;j++){
        dp[j]=dp[j-1]+s[1][j];
    }
    for(int i=2;i<=n;i++){
        dp[1]=dp[1]+s[i][1];
        for(int j=2;j<=m;j++){
            dp[j]=min(dp[j],dp[j-1])+s[i][j];
        }
    }
    cout<<dp[m]<<endl;
    return 0;
 }