题解 | 矩阵的最小路径和

#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
signed main() {
    int n, m;
    cin >> n >> m;
    int a[n][m];
    int dp[2][m];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    dp[0][0] = a[0][0];
    for (int i = 1; i < m; ++i)dp[0][i] = a[0][i] + dp[0][i - 1];
    for (int i = 1; i < n; ++i) {
        dp[i%2][0] = a[i][0] + dp[(i-1)%2][0];
        for (int j = 1; j < m; ++j) {
            dp[i%2][j] = min(dp[(i - 1)%2][j], dp[i%2][j - 1]) + a[i][j];
        }
    }
    cout << dp[(n-1)%2][m - 1] << endl;
}
// 64 位输出请用 printf("%lld")