题解 | 矩阵的最小路径和

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

//const int N=;
int n, m;

int main()
{
    IOS
    cin>>n>>m;
    vector<vector<int>> a(n+1, vector<int>(m+1)), f(n+1, vector<int>(m+1, 1e9));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
    f[1][1]=a[1][1];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            f[i][j]=min({f[i][j], f[i-1][j]+a[i][j], f[i][j-1]+a[i][j]});
    cout<<f[n][m];
    return 0;
}

动态规划，f[i][j]表示从左上角到(i, j)的最小合法值。初始化时f数组为1e9，f[1][1]合法初始化，最后输出f[n][m]即可

#牛客春招刷题训练营#