Bài viết sưu tầm trên mạng.
1. Dãy con đơn điệu dài nhất
Cho dãy $A_1,A_2,…, A_n$. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
Đặc trưng:
- Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử $A$ trong dãy, khác với các bài toán của mô hình 4 [đặc trưng là bài toán đổi tiền], các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
- Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.
Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài: Tam giác bao nhau.
1.2. Công thức QHĐ
Hàm mục tiêu: $f$: độ dài dãy con.
Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi $L_i$ là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ $A_1$ đến $A_i$ và phần tử cuối cùng là $A_i$.
Nhận xét với cách làm này ta đã chia 1 bài toán lớn [dãy con của $n$ số] thành các bài toán con cùng kiểu có kích thước nhỏ hơn [dãy con của dãy $i$ số]. Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
Ta có công thức QHĐ để tính $L_i$ như sau:
- $L_1 = 1$. [Hiển nhiên]
- $L_i = max[1, L_j + 1]$ với mọi phần tử $j$ thỏa mãn: $0