题解 | 矩阵的最小路径和

#include <bits/stdc++.h>
using namespace std;
const int N = 520;
/*

每个位置的最小路径和肯定是从最小的左边或者上面转移过来的，所以有dp[i][j] += min(dp[i-1][j],dp[i][j-1]);
但是有特殊情况就是在第一行的时候，所以特判
if(i==1) dp[i][j] += dp[i][j-1]，最后dp[n][m]就是答案
else if(j==1) dp[i][j] += dp[i-1][j];
*/

int n,m,dp[N][N];

int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>dp[i][j];
        }
    }

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(i==1) dp[i][j] += dp[i][j-1];
            else if(j==1) dp[i][j] += dp[i-1][j];
            else dp[i][j] += min(dp[i-1][j],dp[i][j-1]);
        }
    }

    cout<<dp[n][m];

    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344