DP trên đoạn: thử điểm chia và nhân chuỗi ma trận

Vì sao cần nhớ cả đầu trái lẫn đầu phải r?

Trong nhiều bài, lời giải cho một tiền tố chưa đủ. Khi đặt ngoặc biểu thức, gộp những đống đá kề nhau hoặc chia một đa giác, ta cần biết đáp án cho một phần nằm giữa, chẳng hạn đoạn từ l tới r. Hai chỉ số xác định rõ phần tử đầu, phần tử cuối và nội dung cần xử lý.

DP trên đoạn thường trả lời: đã tối ưu bên trong đoạn này với điều kiện biên nào? Một đoạn ngắn được dùng lại trong nhiều cách chia của các đoạn lớn hơn, nên lưu dp[l][r] tránh tính trùng. Số đoạn phân biệt là O(n²); thời gian còn phụ thuộc số lựa chọn thử cho mỗi đoạn.

Không phải cứ có truy vấn l,r là interval DP. Bài tính tổng đoạn trên mảng tĩnh thường dùng prefix sum; bài cập nhật điểm rồi hỏi min dùng cây đoạn. DP trên đoạn nói về cách tối ưu hoặc đếm bằng các bài toán con trên khoảng, không phải mọi thao tác có hai đầu mút.

Nhân ma trận: đổi ngoặc, không đổi thứ tự

Ma trận p×q nhân với ma trận q×r cho ma trận p×r. Theo cách nhân thông thường, cần p·q·r phép nhân vô hướng. Khi nhân một chuỗi tương thích, phép nhân có tính kết hợp nên có thể đổi ngoặc, nhưng không được đảo thứ tự các ma trận.

Với A kích thước 10×30, B là 30×5, C là 5×60, tính AB trước tốn 10·30·5=1.500, cho ma trận 10×5. Nhân kết quả với C tốn 10·5·60=3.000, tổng 4.500. Tính BC trước tốn 30·5·60=9.000 rồi A(BC) tốn 10·30·60=18.000, tổng 27.000.

Các con số ở đây đếm phép nhân theo mô hình ba vòng lặp thông thường, không phải thời gian mili giây hay tốc độ đo trên một máy. Ta tối ưu thứ tự thực hiện, không thay thuật toán nhân bên trong từng cặp ma trận.

Công thức từ phép nhân cuối cùng

Gọi dim là dãy kích thước, ma trận thứ i có dim[i] hàng và dim[i+1] cột. Đặt dp[l][r] là số phép nhân ít nhất cho chuỗi ma trận l tới r, dùng đoạn đóng ở cả hai đầu trong bài này. Đoạn chỉ có một ma trận không cần nhân, nên dp[i][i]=0.

Trong một cách đặt ngoặc hoàn chỉnh, phép nhân cuối luôn ghép hai khối liên tiếp: l..k và k+1..r, với l<=k<r. Khối trái có kích thước dim[l]×dim[k+1], khối phải là dim[k+1]×dim[r+1]. Chi phí là dp[l][k]+dp[k+1][r]+dim[l]·dim[k+1]·dim[r+1].

Thử mọi k rồi lấy min. Mỗi cách đặt ngoặc có đúng một điểm chia ở phép nhân cuối, nên việc thử không bỏ sót cấu trúc lời giải. Khi đã chốt k, nếu một khối con chưa tối ưu, thay nó bằng cách tốt hơn không đổi kích thước đầu ra, nên không làm hỏng phép ghép cuối. Đó là cơ sở để dùng đáp án tối ưu của hai đoạn con.

Chạy tay theo độ dài

Với dim=[10,30,5,60], ban đầu dp[0][0], dp[1][1], dp[2][2] đều bằng 0. Độ dài 2 chỉ có một vị trí chia; độ dài 3 có hai lựa chọn.

Điền dp[0][2]=4.500. Nếu cần cách đặt ngoặc, lưu điểm k tạo giá trị tốt nhất cho từng ô rồi truy đệ quy hai phía. Code minh họa hiện trả chi phí; nó chưa xuất biểu thức đặt ngoặc.

Một thứ tự sai là duyệt l tăng rồi r tăng mà không xét phụ thuộc. Khi tính dp[l][r], phần dp[k+1][r] có thể chưa xong. Duyệt độ dài tăng bảo đảm cả hai đoạn con đều ngắn hơn đoạn đang xử lý, nên có kết quả trước.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
long long matrix_chain(const vector<long long>& dim){
    int n=(int)dim.size()-1;if(n==0)return 0;
    vector<vector<long long>> d(n,vector<long long>(n,0));
    for(int len=2;len<=n;++len)for(int l=0;l+len<=n;++l){
        int r=l+len-1;d[l][r]=1LL<<60;
        for(int k=l;k<r;++k)
            d[l][r]=min(d[l][r],d[l][k]+d[k+1][r]+dim[l]*dim[k+1]*dim[r+1]);
    }
    return d[0][n-1];
}
int main(){
    int n;vector<long long> dim={10,30,5,60};
    if(cin>>n){dim.resize(n+1);for(auto& x:dim)cin>>x;}
    cout<<matrix_chain(dim)<<'\n';
}

import sys

def matrix_chain(dim):
    n=len(dim)-1
    if n==0:
        return 0
    d=[[0]*n for _ in range(n)]
    for length in range(2,n+1):
        for left in range(n-length+1):
            right=left+length-1
            d[left][right]=min(d[left][k]+d[k+1][right]+dim[left]*dim[k+1]*dim[right+1] for k in range(left,right))
    return d[0][-1]

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    dim=a[1:2+a[0]] if a else [10,30,5,60]
    print(matrix_chain(dim))

Không nhập dữ liệu thì in 4500. Input riêng có n là số ma trận, rồi n+1 kích thước dim. Mỗi ma trận liên tiếp tự tương thích nhờ dùng chung dãy dim; không nhập n cặp độc lập. Với n=1, đáp án 0. Tệp cũng quy ước n=0 trả 0 cho chuỗi rỗng.

Một miền dùng an toàn cho phần số học C++ của ví dụ là 0<=n<=200, mỗi dim là số nguyên từ 1 tới 100.000. Khi đó mỗi tích ba kích thước không quá 10 mũ 15, một cách nhân toàn chuỗi cần tối đa n−1 phép ghép, nên tổng còn dưới INF bằng 2 mũ 60 và vừa long long. Nhân phải được thực hiện trên kiểu rộng ngay từ đầu; chỉ gán kết quả int đã tràn sang long long không sửa được lỗi.

Giới hạn trên mô tả hợp đồng ví dụ và biên số học, không bảo đảm chạy qua mọi thời gian chấm. Python có số nguyên lớn nhưng vẫn chịu chi phí O(n³) của ba lớp lựa chọn. Nếu đề đưa n lớn hơn nhiều, cần xem cấu trúc bổ sung chứ không chỉ đổi ngôn ngữ.

Gộp đá có cùng khung, khác chi phí ghép

Cho các đống đá trên một hàng, mỗi lần gộp hai đống đang kề nhau và trả chi phí bằng tổng số đá của hai đống. Xét phép gộp cuối của đoạn l..r: nó ghép l..k và k+1..r. Lúc này phí ghép là tổng toàn đoạn, không phải tích ba kích thước như ma trận.

Vì vậy có thể đặt dp[l][r]=min qua k của dp[l][k]+dp[k+1][r]+sum(l,r). Dùng prefix sum để đọc sum đoạn O(1); nếu mỗi lần thử k lại quét tổng, bạn có thể thêm một thừa số n không cần thiết. Cơ sở một đống là 0 vì chưa gộp gì.

Với ba đống [1,2,3], gộp 1 và 2 trước tốn 3, rồi gộp với 3 tốn 6, tổng 9. Gộp 2 và 3 trước tốn 5 rồi tốn 6, tổng 11. Ví dụ nhỏ này cho thấy việc thử điểm chia cần thiết, không phải cứ gộp từ trái sang phải là đúng cho mọi input.

Từ hàng sang vòng tròn hoặc đa giác

Đá xếp vòng tròn không có đầu trái cố định. Một cách thường dùng là nhân đôi dãy, giải các đoạn độ dài tới n trên dãy đôi rồi chọn min qua n vị trí bắt đầu. Không lấy đáp án cho cả đoạn dài 2n, vì như vậy đã gộp hai bản sao thay vì một vòng n đống.

Với đa giác, chọn một tam giác liên quan tới cạnh biên có thể chia phần còn lại thành các đoạn đỉnh ngắn hơn. Nhưng phí hoặc điểm số của tam giác do đề quyết định, cùng các điều kiện hợp lệ về hình học. Khung thử điểm chia có thể giống nhau, còn công thức chi phí và biên phải được suy ra riêng.

Một số bài lấy/xóa phần tử cuối hoặc đầu lại chỉ có hai lựa chọn, không thử mọi k, nên thời gian có thể O(n²). Interval DP là cách tổ chức trạng thái, không đồng nghĩa bài nào cũng buộc O(n³).

Độ phức tạp và các tối ưu có điều kiện

Nhân chuỗi ma trận có O(n²) đoạn, mỗi đoạn thử O(n) điểm chia, tổng O(n³) thời gian và O(n²) bộ nhớ. Bảng điểm chia để in ngoặc cũng O(n²). Chỉ lưu một vài hàng gần nhất không hiển nhiên đủ vì một đoạn có thể phụ thuộc nhiều đoạn với đầu mút khác nhau.

Các tối ưu như Knuth hoặc chia để trị DP có điều kiện toán học riêng. Không áp chỉ vì nhìn thấy một min trên k. Ví dụ, tính đơn điệu của điểm tối ưu hoặc tính chất của hàm chi phí phải được chứng minh cho đúng bài, không được suy từ vài bảng nhỏ.

Kiểm bằng mọi cách đặt ngoặc nhỏ

Để tự kiểm tra trên chuỗi ít ma trận (n ≤ 7), bạn có thể viết hàm đệ quy thử mọi vị trí chia k không nhớ để đối chiếu với bảng quy hoạch động trên đoạn theo các ca một ma trận, hai ma trận, ba ma trận và các dãy kích thước lệch nhau.

Khi tự kiểm, dùng hai ma trận để đáp án đúng bằng một tích; dùng ba ma trận có hai cách đặt ngoặc và tính cả hai bằng tay. Thử kích thước rất lệch để thấy lựa chọn tối ưu có thể khác trực giác cân bằng. Nhân ma trận không cho phép sắp xếp lại chuỗi để làm các kích thước trông thuận hơn.

Luyện ngay trên Big-O Coding

Bài nhân dãy ma trận luyện trực tiếp điểm chia cuối. Gộp đá thay phần chi phí ghép bằng tổng đoạn. Gộp đá vòng tròn thêm việc chọn điểm cắt; hãy làm bản hàng trước rồi chỉ thay phần tổ chức đoạn và đáp án cuối, giữ rõ mỗi trạng thái đang chứa những đống nào.

Câu hỏi thường gặp

Nguồn tham khảo

• MIT: Dynamic programming, parenthesization and knapsack
• CP-Algorithms: Introduction to DP
• CSES: Removal Game