Hiểu bài toán

Bài toán yêu cầu tìm chi phí tối thiểu để kết hợp N hũ kẹo dẻo thành một hũ duy nhất. Ban đầu mỗi hũ có độ ngọt a_i. Khi kết hợp hai hũ kề nhau có độ ngọt x và y, ta tạo ra hũ mới có độ ngọt x+y với chi phí là x+y. Vị trí tương đối của các hũ không thay đổi. Đây là bài toán quy hoạch động kẹo dẻo (Gummy Candy Problem) tương tự bài toán 'Minimum Cost to Merge Stones' hoặc 'Matrix Chain Multiplication'.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (O(n^3))

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

const ll INF = 1e18;

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

    int N;
    cin >> N;
    vector<ll> a(N+1);
    for (int i = 1; i <= N; i++) cin >> a[i];

    vector<ll> prefix(N+1, 0);
    for (int i = 1; i <= N; i++) prefix[i] = prefix[i-1] + a[i];

    auto getSum = [&](int l, int r) {
        return prefix[r] - prefix[l-1];
    };

    vector<vector<ll>> dp(N+2, vector<ll>(N+2, 0));

    for (int len = 2; len <= N; len++) {
        for (int l = 1; l + len - 1 <= N; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r],
                               dp[l][k] + dp[k+1][r] + getSum(l, r));
            }
        }
    }

    cout << dp[1][N] << "\n";
    return 0;
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Đây là cách tiếp cận trực tiếp nhất. Ta định nghĩa dp[l][r] là chi phí tối thiểu để kết hợp các hũ từ chỉ số l đến r thành một hũ duy nhất. Công thức truy hồi: dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l, r)) với l ≤ k < r. Ta điền bảng DP theo thứ tự tăng dần độ dài từ 2 đến N. Độ phức tạp O(n^3) do có 3 vòng lặp: độ dài (n), vị trí bắt đầu (n), và vị trí chia (n). Với n ≤ 400, O(n^3) ≈ 64 triệu phép tính, hoàn toàn chấp nhận được.

Cách Quy hoạch động với mảng tổng tiền tố

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

const long long inf = 1e18;
int main(){
    int n;
    cin >> n;
    vector<long long> a(n + 1), sum(n + 1, 0);
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
        sum[i] = sum[i - 1] + a[i];
    }
    vector<vector<long long>> dp(n + 1, vector<long long> (n + 1, 0));
    for(int len = 2; len <= n; len++){
        for(int i = 1; i <= n - len + 1; i++){
            int j = i + len - 1;
            dp[i][j] = inf; 
            for(int k = i; k < j; k++){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    cout << dp[1][n];
    return 0;
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Cách tiếp cận này tương tự cách trên nhưng tối ưu hơn một chút ở cách tính tổng. Thay vì dùng hàm lambda getSum, ta tính mảng tổng tiền tố (prefix sum) trước và truy cập trực tiếp sum[j] - sum[i-1] để lấy tổng đoạn [i, j]. Việc này giúp tránh overhead của hàm và đảm bảo tính nhất quán. Logic DP hoàn toàn giống: dp[i][j] là chi phí kết hợp đoạn [i, j], và ta thử mọi điểm chia k để tìm giá trị tối thiểu.

Cách Quy hoạch động với kích thước bảng cố định

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

const int MAXN = 405;
long long dp[MAXN][MAXN], prefix[MAXN];

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i-1] + a[i];
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i+len-1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]);
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Đây là biến thể sử dụng mảng tĩnh cố định kích thước MAXN thay vì vector động. Điều này có thể nhanh hơn một chút trong một số trường hợp do tránh việc cấp phát động, nhưng về cơ bản thuật toán vẫn là quy hoạch động O(n^3). Ta dùng LLONG_MAX để khởi tạo giá trị vô cực. Bảng dp được điền theo độ dài (len) tăng dần để đảm bảo các giá trị cần thiết đã được tính toán trước khi dùng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất quy hoạch động: chi phí để kết hợp một đoạn phụ thuộc vào chi phí của các đoạn con bên trong.
• Công thức truy hồi: dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum(l, r)) với mọi k từ l đến r-1.
• Phải tính tổng đoạn [l, r] nhanh chóng để không làm tăng độ phức tạp lên O(n^4). Dùng mảng tổng tiền tố (prefix sum) là chìa khóa.
• Thứ tự tính toán: phải tính các đoạn ngắn trước (len = 2), sau đó mới tính các đoạn dài hơn (len = 3, 4, ..., n).

Lỗi thường gặp

• Quên tính tổng tiền tố và dùng vòng lặp lồng để tính tổng mỗi lần, dẫn đến độ phức tạp O(n^4) và TLE.
• Khởi sai giá trị vô cực (INF): phải đủ lớn (ví dụ 1e18) để không bị tràn số khi cộng dồn.
• Lỗi chỉ số mảng: khi dùng vector hoặc mảng, cần chú ý độ dài và cách truy cập (0-based hoặc 1-based) để tránh truy cập ngoài vùng nhớ.
• Không kiểm tra điều kiện biên: vòng lặp k chạy từ l đến r-1, không chạy đến r vì không thể chia đoạn [i, j] tại điểm j (phải chia thành [i, j] và [j+1, j] là vô lý).