C++ 代码

一道区间dp本小菜花了一番时间思考

//
// Created by ASUS on 8/9/2021.
//
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n, a[2100][2100], dp[2100];

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> a[i][j];
        }
        dp[i]=inf;
    }
    for(int i=n-1;i>=1;i--){
        for(int j=i;j<=n;j++){
            dp[i]=min(dp[i],dp[j]+a[i][j]);
        }
    }
    cout << dp[1];
    return 0;
}