题解 | 矩阵的最小路径和

#include <iostream>
#include <cstring>

#define N 2010

using std::cin;
using std::cout;

int dp[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;

    // 0. input
    int n, m; cin >> n >> m;
    int tmp;

    // 1. main logic
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> tmp;
            dp[j] = std::min(dp[j], dp[j-1]) + tmp;
        }
        dp[0] = 0x7fffffff;
    }

    // 2. output
    cout << dp[m];

    return 0;
}

优化了空间复杂度