题解 | 矩阵的最小路径和

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    const int INF = 1e9;
    vector<int> dp(m, INF);          // dp[j]: 走到当前行第 j 列的最小和

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            if (i == 0 && j == 0) dp[0] = x;                 // 起点
            else if (j == 0)        dp[j] = dp[j] + x;       // 只能从上面来
            else                    dp[j] = min(dp[j], dp[j - 1]) + x; // 上/左取小
        }
    }

    cout << dp[m - 1] << '\n';        // 终点
    return 0;
}