Dưới đây là hướng dẫn giải bài toán Xâu con chung dài nhất (LCS) theo quy trình 3 bước của Quy hoạch động:
1. Định nghĩa trạng thái
Gọi là độ dài của xâu con chung dài nhất của xâu con gồm ký tự đầu tiên () và xâu con gồm ký tự đầu tiên ().
- Chỉ số chạy từ đến (độ dài xâu ).
- Chỉ số chạy từ đến (độ dài xâu ).
- Kết quả cuối cùng của bài toán sẽ nằm ở .
2. Công thức chuyển trạng thái
Để tính , ta xét ký tự cuối cùng hiện tại của hai xâu là và :
-
Trường hợp 1: Nếu ký tự
- Ký tự này chắc chắn thuộc xâu con chung dài nhất.
- Công thức:
- (Ý nghĩa: Lấy kết quả của hai xâu trước đó rồi cộng thêm 1 đơn vị cho ký tự trùng nhau vừa tìm thấy).
-
Trường hợp 2: Nếu ký tự
- Ký tự cuối của ít nhất một trong hai xâu không thuộc xâu con chung đang xét (hoặc cả hai đều không thuộc). Ta sẽ chọn kết quả tốt nhất khi bỏ đi hoặc bỏ đi .
- Công thức:
3. Trạng thái cơ sở
Trạng thái cơ sở là khi một trong hai xâu là xâu rỗng (độ dài bằng 0). Khi đó, xâu con chung của chúng chắc chắn có độ dài bằng 0.
- với mọi (Xâu rỗng).
- với mọi (Xâu rỗng).
Đánh giá độ phức tạp: .