Nhân chuỗi ma trận (Giải pháp O(N³)) trong C++

Cho một chuỗi ma trận, cần tìm số phép nhân tối thiểu bằng cách chọn trình tự nhân đúng.

Nhân ma trận có tính kết hợp, ví dụ 4 ma trận ABCD có thể nhân theo A(BCD), (AB)(CD), (ABC)D, A(BC)D. Nhiệm vụ tìm thứ tự hiệu quả nhất.

Đầu vào là mảng arr[] = {1, 2, 3, 4} nghĩa là các ma trận có kích thước (1×2), (2×3), (3×4).

Đầu vào

Thứ tự các ma trận: {1, 2, 3, 4} → {(1×2), (2×3), (3×4)}

Đầu ra

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

Thuật toán

matOrder(array, n)
Đầu vào: Danh sách ma trận, số lượng ma trận.
Đầu ra: Số phép nhân ma trận tối thiểu.
Bắt đầu
    định nghĩa bảng minMul kích thước n×n, điền 0
    cho length := 2 đến n, làm
        cho i := 1 đến n-length, làm
            j := i + length - 1
            minMul[i, j] := ∞
            cho k := i đến j-1, làm
                q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
                nếu q < minMul[i, j], thì
                    minMul[i, j] := q
                kết thúc nếu
            kết thúc
        kết thúc
    kết thúc
    trả về minMul[1, n-1]
Kết thúc

Ví dụ mã C++

#include<iostream>
using namespace std;

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

int main(){
    int arr[] = {1, 2, 3, 4};
    int size = 4;
    cout << "Số phép nhân ma trận tối thiểu: "<<matOrder(arr, size);
}

Kết quả đầu ra

Số phép nhân ma trận tối thiểu: 18