Nhân chuỗi ma trận (Matrix Chain Multiplication) trong C

Cho dãy ma trận với kích thước arr[0]×arr[1], arr[1]×arr[2], ... Tìm thứ tự nhân để số phép nhân tối thiểu.

Ví dụ

Đầu vào - arr[] = {3, 4, 5, 6}

Ma trận: M1(3×4), M2(4×5), M3(5×6)

Cách 1: M1×(M2×M3) = 3×4×6 + 4×5×6 = 72+120=192

Cách 2: (M1×M2)×M3 = 3×4×5 + 3×5×6 = 60+90=150 ← tối ưu

Quy hoạch động

• minMul[i][j]: số phép nhân tối thiểu nhân ma trận i đến j
• Cơ sở: minMul[i][i] = 0
• Đệ quy: minMul[i][j] = min(minMul[i][k] + minMul[k+1][j] + arr[i-1]×arr[k]×arr[j])
• Điền bảng theo độ dài chuỗi L=2 đến n-1

Chương trình mẫu

#include <stdio.h>
#include <limits.h>

int matrixChainOrder(int arr[], int n) {
    int minMul[n][n];
    
    for (int i = 1; i < n; i++)
        minMul[i][i] = 0;
    
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n-L+1; i++) {
            int j = i + L - 1;
            minMul[i][j] = INT_MAX;
            for (int k = i; k <= j-1; k++) {
                int q = minMul[i][k] + minMul[k+1][j] + arr[i-1]*arr[k]*arr[j];
                if (q < minMul[i][j])
                    minMul[i][j] = q;
            }
        }
    }
    return minMul[1][n-1];
}

int main() {
    int arr[] = {3, 4, 5, 6, 7, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Số phép nhân tối thiểu: %d\n", matrixChainOrder(arr, n));
    return 0;
}

Kết quả

Số phép nhân tối thiểu: 444

Độ phức tạp: O(n³) thời gian, O(n²) bộ nhớ. Có thể tối ưu hơn với Knuth optimization O(n²) trong trường hợp đặc biệt.