题解 | 矩阵的最小路径和

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
//#define int long long
using vi = vector<int>;
using vvi = vector<vector<int>>;

void solve() {
    int n, m;cin >> n >> m;
    vvi a(n, vi(m));
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    vvi dp(n + 1, vi(m + 1, 1e9));
    dp[1][0] = 0;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            dp[i + 1][j + 1] = min(dp[i][j + 1] + a[i][j], dp[i + 1][j] + a[i][j]);
        }
    }
    cout << dp[n][m] << endl;
}


/*

*/


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

经典dp，注意这题会卡#define int long long，只有32mb ll会超内存