Dãy con chung dài nhất

Dãy con chung dài nhất (Longest Common Subsequence, LCS) là một bài toán kinh điển trong khoa học máy tính, yêu cầu tìm dãy con dài nhất xuất hiện trong hai dãy. Dãy con là một dãy có thể tạo ra từ một dãy khác bằng cách xóa một số hoặc không xóa phần tử nào mà vẫn giữ nguyên thứ tự của các phần tử còn lại.

Ví dụ, xét hai dãy sau:

S1 = "AGGTAB"

S2 = "GXTXAYB"

LCS của S1 và S2 là "GTAB", có độ dài bằng 4.

Có một số cách giải bài toán LCS, trong đó cách phổ biến nhất là quy hoạch động.