空间优化

可以优化成一维的.

$f_{i,j}=\min(f_{i-1,j},f_{i,j-1})+a_{i,j}$ 可以优化成 $f_j=\min(f_j,f_{j-1})+a_{i,j}$.

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

constexpr int N=110;
int f[N],a[N];

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

    memset(f,0x3f,sizeof(f)),f[1]=0;
    for(int i=1;i<=n;++i)
        for(int j=1,x;j<=n;++j){
            cin>>x;
            f[j]=min(f[j],f[j-1])+x;// f[i][j] = min(f[i-1][j],f[i][j-1])
        }
    cout<<f[n];

    return 0;
}