DP_ part 3

II.3.LCS dãy con chung dài nhất

Ta xét bài toán sau:
Cho 2 xâu, tìm xâu con chung dài nhất của chúng.  độ dài của mỗi xâu <= 1000


Định nghĩa: Giống như dãy con
Giải:
Gọi 2 xâu là a, b có độ dài lần lượt là lena, lenb.  
Bây giờ ta xét:
+ Kết quả muốn cho ra : độ dãy xâu con chung dài nhất
+ Dữ liệu xoay quanh: 2 xâu con
Do đó ta sẽ có 1 công thức qhđ:
Gọi F[i][j] = độ dài xâu con chung dài nhất của i phần từ đầu của a và j phần tử đầu của b

Bây giờ hãy xem xem F[i][j] được tính như nào
+ Rõ ràng, F[i][j] >= F[i][j-1] và F[i-1][j] . ( Nhận ra bằng trực giác) --> ban đầu F[i][j] = max( F[i-1][j] , F[i][j-1] )
+ Ngoài ra nếu a[i] = b[j] thì : F[i][j] =F[i-1][j-1] + 1
--> Công thức : F[i][j] = max(F[i-1][j] , F[i][j-1] ) nếu a[i] = b[j] --> F[i][j] = max(F[i][j], F[i-1][j-1] + 1).

code: http://ideone.com/PGkTr2 Link bài : 
+ Hãy thử mở rộng lên 3 , 4 , 5... 6 xâu :)
+ http://vn.spoj.com/problems/QBSTR/
+ http://www.usaco.org/index.php?page=viewproblem2&cpid=126
Các nguồn tham khảo:
+ http://www.algorithmist.com/index.php/Longest_Common_Subsequence