Tìm dãy con chung dài nhất của hai dãy số

[Quoc_Khanh_Bui (True Blue)]

Cho hai dãy số nguyên (a1,a2,…,am), (b1,b2,…,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên.
Mình không hiểu gì lắm về quy hoạch động và cả bài trên nữa, rất mong nhận được sự giúp đỡ của mọi người về một vài câu hỏi dưới đây:

1. Bài toán con của bài toán trên là gì?
2. Tại sao ai <> bj thì l[i,j]=max{l[i-1,j], l[i,j-1]}
   và ai = Bj thì l[i,j]= 1+l[i-1,j-1] ?

Xin cảm ơn!

[Rok_Hoang (Minh Hoàng)]

1. Bài toán con là tìm dãy con chung của (a1,a2,…a(m-1)) và (b1,b2,…,bn).
2. ai<>bj có nghĩa là độ dài dãy con trung sẽ là của (a1->a(i-1)) và b hoặc là chung của a và (b1->b[j-1])
   ai=bj có nghĩa là độ dài dãy con chung của (a1->a(i-1)) và (b1->b(j-1)) cộng thêm 1 là cặp chung (ai,bj)

[Quoc_Khanh_Bui (True Blue)]

Mình chưa hiểu lắm, lấy ví dụ hai dãy số là [1,3,2,5,6,7] và [1,9,2,5,6,3], vậy thì dãy con chung dài nhất sẽ là [1,2,5,6] .

• Như vậy thì bài toán con cần tìm là tìm dãy con chung của [1] và [1,9,2,5,6,3] ; sau đó là [1,3] và [1,9,2,5,6,3] … cho tới [1,3,2,5,6] và [1,9,2,5,6,3]
  nhưng làm sao mình có thể xây dựng nghiệm từ những bài toán con trên?

[Rok_Hoang (Minh Hoàng)]

Bạn có thể xây dựng nghiệm từ bài toán nhỏ hơn: mảng a 1 phần tử, mảng b 1 phàn tử, rồi tiếp theo mảng a 2 phần tử, mảng b 1 phần tử,…
Bạn lên youtube xem thuật toán như thế nào cho dễ hình dung

[Quoc_Khanh_Bui (True Blue)]

Mình vẫn không biết phải làm sao để tìm nghiệm từ nghiệm của các bài toán con

[Nguyen_Tuan_Anh2 (Nguyễn Tuấn Anh)]

Công thức đây nhé
gọi l[i,j] là độ dài dãy con chung của A, B ta có:
L[i,j]:= max(l[i-1,j],l[i,j-1], l[i-1,j-1] +x);
nếu a[i]=b[j] thì x=1;
nếu a[i]<>b[j] thì x=0;

[tarzan115 (Tarzannnnnn)]

Mình chưa hiểu lắm, lấy ví dụ hai dãy số là [1,3,2,5,6,7] và [1,9,2,5,6,3], vậy thì dãy con chung dài nhất sẽ là [1,2,5,6] .

• Như vậy thì bài toán con cần tìm là tìm dãy con chung của [1] và [1,9,2,5,6,3] ; sau đó là [1,3] và [1,9,2,5,6,3] … cho tới [1,3,2,5,6] và [1,9,2,5,6,3]
  nhưng làm sao mình có thể xây dựng nghiệm từ những bài toán con trên?

theo như ví dụ này bạn đưa ra thì kết quả sai so với yêu cầu bài toán rồi bạn ạ.
người ta bắt tìm dạy con chung lớn nhất, tức là 1 “dãy” chứ không phải tìm các “phần tử” chung của 2 mảng.
theo ví dụ này thì dãy con chung lớn nhất của 2 mảng sẽ là [2,5,6]

[vanthanhbinhlong (Nguyen Van Thanh)]

Video hướng dẫn cụ thể giải bài này tại đây nhé https://www.youtube.com/watch?v=CueoltqwF5g

[nhatlonggunz]

Bạn có thể google Longest Common Subsequence.
Còn dãy con liên tiếp thì sửa công thức lại chút thôi.

[rogp10]

L(i,j) chính là độ dài dãy con chung của a[1…i] và b[1…j], vậy cái ta cần tìm là L(m,n). Vậy L(i,j) tính ntn?

• L(i,j) = 0 với i=0 hoặc j=0
• Nếu a[i] = b[j] thì có phải là dãy con chung được kéo dài ra không
• Ngược lại ta có 3 phương án. Chọn max trong số đó.

[phamkhanhhand (Khánh Hà)]

cái bài tìm dãy con chung có 2 kiểu:
Trường hợp 1-tìm dãy con chung dài nhất của xâu: ở đây dãy con là 1 đoạn của dãy cha => vị trí của các phần tử trong dãy con phải có vị trí trước sau và liền kề.
Trường hợp 2-Tìm dãy con chung dài nhất (của dãy số): dãy con ở đây lại khác ở trên, dãy con tạo thành do xóa bớt một số phần tử trong dãy cha đi => vị trí có thể không cần liền kề, chỉ cần theo thứ tự trước sau thôi

PS: Mình vẫn nghĩ là đã gọi là dãy con thì nó phải là 1 đoạn của dãy cha (trường hợp 1). Chứ xóa đi phần tử thì sao gọi là dãy con được.
vd: dãy cha là : abc
=> tất cả dãy con là: a, b, c, ab, bc, abc
=> các cái không phải dãy con là: ac -> cái này nếu vào trường hợp 2 (xóa bớt phần tử) thì lại đúng

[rogp10]

Đó là hai bài khác nhau. Bài 1 giải bằng QHĐ cỡ O(mn) time và O(max(m,n)) mem, nếu là string thì dùng suffix tree để được O(m+n) time.