Cách nghĩ bài Quy hoạch động Dãy con tăng dài nhất LIS

Loạt bài Quy hoạch động cơ bản mình trình bày ở đây nhằm mục đích định rõ các bước tư duy cụ thể để đưa ra được thuật toán Quy hoạch động cho một bài toán. Sản phẩm của quá trình lập luận, suy nghĩ gồm có: định nghĩa hàm trạng thái mô tả một trạng thái chung của bài toán; một công thức Quy hoạch động thể hiện việc tính toán các trạng thái sau nhờ một vài trạng thái trước đó; một số bài toán cơ sở làm tiền đề cho việc tính các trạng thái sau và một phương án lưu trữ giá trị các trạng thái nhằm mục đích đưa ra kết quả cuối cùng hoặc truy vết tìm một phương án hợp lí.

Bài này sẽ bàn về một bài Quy hoạch động điển hình "Dãy con tăng dài nhất". Có thể bạn đã đọc, thấy bài này ở nhiều nơi rồi, ở bài viết này mình một lần nữa phân tích theo 5 bước cụ thể để các bạn mới học có thể tiếp cận một cách dễ dàng hơn.

Tóm tắt bài Dãy con tăng dài nhất (LIQ): Cho dãy gồm N phần tử a[i] với i từ 1 tới N; Hãy tính độ dài của dãy con tăng đơn điệu dài nhất. Một dãy con tăng đơn điệu là một dãy a[i1], a[i2],..., a[ik] thỏa mãn điều kiện i1<i2<...<ik và a[i1]<a[i2]<...<a[ik].

Bước 1: Định nghĩa hàm trạng thái. Theo đề bài ta thấy, cần tìm độ dài dãy con tăng đơn điệu dài nhất trong dãy N phần tử --> gọi F(i) là độ dài dãy con tăng đơn điệu dài nhất tính từ phần tử a[1] đến a[i] và phần tử kết thúc dãy đơn điệu tăng là a[i]. 

Bước 2: Xác định công thức Quy hoạch động. Giả sử ta đang xét dãy có phần tử cuối cùng là a[i]; khi đó F(i) là độ dài dãy con tăng đơn điệu dài nhất khi tính đến phần tử a[i]; Vậy trước trạng thái F(i) có thể là gì? Đó là dãy con dài nhất kết thúc ở phần tử a[j] trước đó với j<i, j=1..(i-1); khi nối thêm a[i] vào dãy đơn điệu đó (a[j]<a[i]); khi đó F(i)=max{F(j)}+1 với j=1...i-1 và a[j]<a[i]

Ví dụ: Dãy A={-7, 10, 9, 2, 3, 8, 8, 1} Bạn có thể thực hành với dãy ví dụ này để thấy cách mở rộng dãy khi xét tới phần tử a[i]

• F(1) = 1 do phần tử đầu tiên tạo thành 1 dãy con (lis1) thỏa mãn đk {-7}
• Xét phần tử a[2]=10; ta có thể nối dãy lis1 với 10 để thành lis2 = {-7, 10]; khi này ta có F(2)=2.
• Xét a[3]=9; ta có thể nối 9 với lis1 {-7} thành {-7,9} có độ dài 2; không thể nối lis2 {-7, 10} được vì không thỏa mãn dãy đơn điệu tăng --> như vậy F(3)=2
• Xét a[4]=2, có thể nối 2 vào dãy lis1 {-7} để thành {-7, 2} và độ dài là 2; không thể nối với dãy {-7, 10} hay {-7, 9} hay {10} hoặc {9} vì không tạo dãy đơn điệu tăng được; như vậy F(4)=2

Bước 3: Xác định cơ sở Quy hoạch động. Ta xét dãy chỉ có 1 phần tử a[i] sẽ luôn là dãy tăng đơn điệu nên F(i)=1 với mọi i;

Bước 4: Xây dựng bảng phương án. Ta tính lại các F(i) --> Lưu các giá trị vào mảng 1 chiều F[i] với F[i]=1 ban đầu. Tính lần lượt các F[] khác sử dụng vòng lặp.

Bước 5: Khi tính được các F[i] là độ dài dãy con tăng đơn điệu dài nhất kết thúc ở mỗi phần tử a[i] -> Kết quả cần tìm là dãy con tăng đơn điệu dài nhất có thể nên sẽ là max{F[i]}

Code mẫu phần QHĐ bài Dãy con tăng LIQ bản dễ:

vector<int> f(n, 1); //Lưu bảng phương án
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                maximize(f[i], f[j] + 1);

    int res = *max_element(f.begin(), f.end());