Hiểu bài toán

Bài toán yêu cầu tìm cách đặt dấu ngoặc sao cho số phép nhân thực hiện khi nhân chuỗi các ma trận là ít nhất. Cho trước n ma trận, ma trận thứ i có kích thước ai x a{i+1}. Chi phí để nhân hai ma trận A (p x q) và B (q x r) là pqr. Với tính kết hợp của phép nhân, thứ tự đặt ngoặc khác nhau dẫn đến tổng chi phí khác nhau. Với n ma trận, có Ct(n) cách đặt ngoặc khác nhau (số Catalan), không thể thử tất cả. Ta cần sử dụng quy hoạch động để tìm chi phí tối thiểu.

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

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
long long dp[502][502];
long long a[502];
int main(){
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
        cin >> a[i];
    // dp[i][j]: chi phí tối thiểu để nhân ma trận i đến j
    // Ma trận i có kích thước a[i-1] x a[i]
    // Ma trận j có kích thước a[j-1] x a[j]
    // dp[i][j] = min(dp[i][k] + dp[k+1][j] + a[i-1]*a[k]*a[j])
    for (int len = 2; len <= n; len++){ // len là độ dài chuỗi ma trận cần nhân
            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++){
                    // Ma trận i..k và k+1..j
                    // Ma trận i..k có kích thước a[i-1] x a[k]
                    // Ma trận k+1..j có kích thước a[k] x a[j]
                    // Kết quả có kích thước a[i-1] x a[j]
                    long long cost = dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j];
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
    }
    cout << dp[1][n] << endl;
    return 0;
}

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

Đây là cách tiếp cận chuẩn cho bài toán nhân ma trận tối ưu (Matrix Chain Multiplication).

1. Định nghĩa trạng thái: dp[i][j] là số phép nhân tối thiểu để tính tích các ma trận từ ma trận thứ i đến ma trận thứ j (theo code mẫu, i và j chạy từ 1 đến n).
2. Cơ sở: dp[i][i] = 0 (chỉ một ma trận, không cần nhân). Trong code, mảng dp mặc định là 0 nên ta không cần khởi tạo thủ công cho các đường chéo.
3. Công thức chuyển trạng thái: Để tính dp[i][j], ta chia đoạn [i, j] thành hai phần tại một điểm k (i <= k < j). Ta nhân đoạn [i, k] trước, đoạn [k+1, j] sau, rồi nhân hai kết quả đó với nhau. Chi phí = dp[i][k] (chi phí bên trái) + dp[k+1][j] (chi phí bên phải) + a[i-1] * a[k] * a[j] (chi phí nhân hai kết quả). Ta lấy giá trị nhỏ nhất qua các vị trí k.
4. Thứ tự tính: Tính độ dài len tăng dần từ 2 đến n.

Lưu ý chỉ số trong code: Input a[0]...a[n]. Ma trận i (từ 1 đến n) có kích thước a[i-1] x a[i]. Khi chia tại k, ma trận bên trái có kích thước a[i-1] x a[k], ma trận bên phải có kích thước a[k] x a[j]. Chi phí nhân hai kết quả là a[i-1] * a[k] * a[j].

Cách Brute Force (Đệ quy có nhớ)

// Ý tưởng: Dùng đệ quy để thử tất cả các cách chia
// Để tránh tính toán lại, dùng mảng memo
#include <bits/stdc++.h>
using namespace std;

long long memo[505][505];
long long a[505];
int n;

long long solve(int l, int r) {
    if (l == r) return 0;
    if (memo[l][r] != -1) return memo[l][r];

    long long res = LLONG_MAX;
    for (int k = l; k < r; k++) {
        long long cost = solve(l, k) + solve(k + 1, r) + a[l] * a[k + 1] * a[r + 1];
        if (cost < res) res = cost;
    }
    return memo[l][r] = res;
}

int main() {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];
    memset(memo, -1, sizeof(memo));
    // Ma trận từ 0 đến n-1
    cout << solve(0, n - 1);
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất.

1. Hàm solve(l, r) tính chi phí tối thiểu cho đoạn ma trận từ l đến r.
2. Nếu l == r, trả về 0.
3. Nếu đã tính rồi, trả về giá trị trong memo.
4. Thử mọi vị trí chia k từ l đến r-1, tính chi phí, và lưu giá trị nhỏ nhất.

Về mặt bản chất, đây là Top-down DP, độ phức tạp tương đương Bottom-up DP.

Cách Optimization: Knuth Optimization (Người dùng cung cấp)

// Code mẫu cho Knuth Optimization
// Chỉ hoạt động khi bài toán thỏa mãn tính chất Quadrangle Inequality
// Giả sử các giá trị a[i] đều dương nên thỏa mãn điều kiện
#include <bits/stdc++.h>
using namespace std;

long long dp[505][505];
long long a[505];
int K[505][505]; // Lưu vị trí k tối ưu
int n;

int main() {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
        K[i][i] = 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;
            // Vòng lặp k chỉ chạy từ K[i][j-1] đến K[i+1][j]
            int start = K[i][j-1];
            int end = (i+1 <= n) ? K[i+1][j] : j-1;

            for (int k = start; k <= end; k++) {
                long long cost = dp[i][k] + dp[k+1][j] + a[i-1]*a[k]*a[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    K[i][j] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

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

Bài toán nhân ma trận tối ưu có thể áp dụng tối ưu hóa Knuth để giảm độ phức tạp từ O(n^3) xuống O(n^2). Điều kiện áp dụng: Đạo hàm thứ hai của hàm chi phí >= 0 (trong bài này là dương). Thay vì duyệt toàn bộ k từ i đến j-1, ta chỉ cần duyệt trong khoảng [K[i][j-1], K[i+1][j]]. Lưu ý: Giải thuật này chỉ đúng khi các ma trận có kích thước dương, điều kiện thường thỏa mãn trong đề bài.

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

Bài học kinh nghiệm

• Bài toán có cấu trúc 'Optimal Substructure' (Cấu trúc tối ưu con) và 'Overlapping Subproblems' (Các bài toán con chồng lặp), phù hợp với Dynamic Programming.
• Cần chú ý quan hệ giữa kích thước ma trận input (a[i]) và chỉ số ma trận trong công thức DP.
• Giải pháp O(n^3) với n <= 500 là đủ tốt (~1.25 * 10^8 phép tính), nhưng với n lớn hơn hoặc để tối ưu, Knuth Optimization là lựa chọn tốt.

Lỗi thường gặp

• Lỗi chỉ số mảng:混淆 ma trận thứ i với kích thước a[i]. Ma trận i có kích thước a[i-1] x a[i] (nếu dùng 1-based indexing cho mảng a).
• Tràn số (Overflow): Chi phí nhân ma trận có thể rất lớn (100010001000 * 500), cần dùng kiểu long long.
• Khởi tạo DP: Cần đảm bảo các giá trị ban đầu (dp[i][i]) là 0.