Gọi ~dp[i][j]~ là chi phí nhỏ nhất để ghép các cục thạch thứ ~i~ tới cục thạch thứ ~j~.

Để tính ~dp[i][j]~, ta muốn ghép hai cục thạch nhỏ hơn đã được ghép trong đoạn ~[i, j]~.

Ta duyệt qua tất cả ~k~ trong đoạn ~[i,j-1]~ và thử kết hợp hai cục thạch được tạo từ đoạn ~[i,k]~ và ~[k+1,j]~.

Chi phí thực hiện điều trên là ~dp[i][k] + dp[k+1][j] + a[i] + a[i+1] + ... + a[j]~. Để tính ~a[i] + a[i+1] + ... + a[j]~ ta có thể sử dụng mảng cộng dồn.

Độ phức tạp tính toán là ~O(N^3)~.

Bạn có thể tối ưu hơn nữa bằng KNUTH'S OPTIMIZATION (bài viết được viết bằng tiếng Anh).

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

const int MAXN = 400;
const long long INF = 0x3f3f3f3f3f3f3f3f;

long long query(vector<long long>& p, int l, int r){
    if( l == 0 ){
        return p[r];
    }
    else return p[r] - p[l - 1];
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin >> n;
    vector<long long> a(n), p(n);
    for (long long& x : a) cin >> x;
    for (int i = 0; i < n; ++i)
        p[i] = (i == 0 ? 0 : p[i - 1]) + a[i];

    static long long dp[MAXN][MAXN];
    memset(dp, 0x3f, sizeof(dp));

    for (int i = 0; i + 1 < n; ++i) dp[i][i + 1] = a[i] + a[i + 1];

    for (int i = 0; i < n; ++i) dp[i][i] = 0;

    for (int i = n - 1; i >= 0; --i)
        for (int j = i + 2; j < n; ++j) {
            long long best = INF;
            for (int k = i; k < j; ++k)
                best = min(best, dp[i][k] + dp[k + 1][j]);
            dp[i][j] = query(p, i, j) + best;
        }
    cout << dp[0][n - 1] << '\n';

    return 0;
}