Dynamic programming là gì Update 10/2024

Bài viết gốc: https://manhhomienbienthuy.bitbucket.io/2017/Aug/24/algorithm-dynamic-programming.html (đã xin phép tác giả

Đường đi dài nhất từ q -> t sẽ là q -> r -> t hoặc q -> s -> t. Nhưng không giống như bài toán tìm đường đi ngắn nhất, đường đi dài nhất không phải là tổ hợp của những đường đi thành phần, do đó, bài toán này không có cấu trúc con tối ưu.

Bạn đang xem: Dynamic programming là gì

Ví dụ, đường q -> r -> t không phải là tổ hợp của đường đi dài nhất từ q -> r và đường đi dài nhất từ r -> t. Bởi vì, đường đi dài nhất q -> r phải là q -> s -> t -> r và đường đi dài nhất từ r -> t phải là r -> q -> s -> t.

Một số bài toán quy hoạch động

Trong phần này, chúng ta sẽ làm quen với quy hoạch động thông qua một số ví dụ cụ thể. Chúng ta sẽ xem xét cách quy hoạch động được áp dụng vào các bài toán cụ thể như thế nào, đồng thời qua đó, chúng ta sẽ hiểu hơn về các tính chất ở phần trước.

Ví dụ 1: Bài toán kinh điển với đồng xu

Đây là một ví dụ rất kinh điển khi học về quy hoạch động. Có thể có nhiều cách phát biểu khác nhau nhưng về cơ bản, nội dung của nó sẽ tương tự như sau.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, …, Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là không giới hạn.

Với bài toán này, chúng ta cần xây dựng và giải các bài toán con gối nhau. Với ví dụ của chúng ta, mỗi bài toán con dp(P) với P là bài toán tìm số đồng xu nhỏ nhất để khối lượng của chúng là P. và dp(P) = k chính là số lượng đồng xu nhỏ nhất đó.

Chúng ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán con dp(0) sau đó tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ được xây dựng lần lượt cho đến chúng ta xây dựng đến bài toán dp(S) và đó chính là kết quả của bài toán lớn. Một điều cần lưu ý với kỹ thuật này là bài toán con tiếp theo sẽ không thể giải được nếu chúng ta chưa giải bài toán con trước đó.

Cuối cùng là phần khó nhất của mọi bài toán quy hoạch động, đó là trả lời câu hỏi: cấu trúc con tối ưu của bài toán này ở đâu. Hay nói một cách khác, làm thế nào để từ những bài toán nhỏ hơn có thể tổ hợp ra lời giải cho bài toán lớn. Với vị dụ kinh điển này, mọi thứ sẽ tương đối đơn giản, nhưng với những bài toán phức tạp hơn, chúng ta cần suy nghĩ và tính toán nhiều hơn.

Quay trở lại với bài toán của chúng ta. Giả sử P là tổng khối lượng của các đồng xu nặng lần lượt là V1, V2, …, Vj. Để có được khối lượng P, chúng ta cần thêm vài đúng 1 đồng xu nặng U vào khối lượng Q sao cho Q + U = P. Tất nhiên, bài toán con dp(Q) chúng ta đã có lời giải nên chúng ta sẽ biết được cần bao nhiêu đồng xu cho dp(P). Và vì có nhiều đồng xu U (nhiều nhưng hữu hạn) nên chúng ta có thể cần đến nhiều bài toán con trước đó, và dp(p) là giá trị nhỏ nhất sau khi tổng hợp những bài toán con đó.

Ví dụ với n = 3, S = 11, W = .

Bắt đầu với bài toán con 0 ta có dp(0) = 0Với bài toán con 1, có 1 đồng xu (nặng 1) có thể thêm vào từ 0 đồng xu nào cả. Vậy dp(1) = dp(0) + 1 = 1.Với bài toán con 2, cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ 1 đồng xu. Vậy dp(2) = dp(1) + 1 = 2.Với bài toán con 3, chúng ta có thể thêm 1 đồng xu 3 vào 0 đồng xu hoặc thêm 1 đồng xu 1 vào 2 đồng xu. Rõ ràng là cách đầu tiên cho kết quả nhỏ hơn. Vậy dp(3) = min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1…Cứ tiếp tục như vậy cho đến bài toán S chính là đáp án chúng ta cần tìm.

Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ của chúng ta, mảng dp sẽ lưu kết quả cho từng bài toán con. Nói cách khác, dp

= k nghĩa là cần ít nhất k đồng xu để có khối lượng là P Toàn bộ mảng này sẽ được tính bằng vòng lặp. Đoạn code sau mô tả toàn bộ quá trình này.

n, S = map(int, input().split())w = list(map(int, input().split()))dp = * (S + 1)dp = 0for P in range(1, S + 1): dp

= min(dp

for x in w if x P) + 1print(dp)print(dp)# Nếu đầu vào như sau: n = 3, S = 11, w = # Thì bảng lời giải cho các bài toán con sẽ lần lượt như sau:# P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11# ——+–+–+–+–+–+–+–+–+–+–+–# k = 0 |1 |2 |1 |2 |1 |2 |3 |2 |3 |2 |3

Ví dụ 2: Xâu con chung dài nhất (LCS)

Thêm một ví dụ nữa cho dễ, cũng là một bài toán rất nổi tiếng.

Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu “quetzalcoatl” và “tezcatlipoca” thì xâu con chung dài nhất sẽ là “ezaloa” với độ dài 6.

Với bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:

Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con được lấy ra đó. Dễ dàng thấy được rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, dp(i, j). Và bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con lần lượt từ dp(0, 0) và tăng dần độ dài xâu được lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài.

Chúng ta hãy bắt đầu lần lượt các bài toán con. Đương nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy dp(0, j) = dp(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần suy xét một vài trường hợp.

Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hưởng gì đến kết quả. Công thức ở đây sẽ là dp(i, j) = dp(i – 1, j).Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả thì dp(i, j) = dp(i, j – 1).Trường hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức là x1 == x2. Trong trường hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng là dp(i, j) = dp(i – 1, j – 1) + 1.

Trong cả ba trường hợp trên, chúng ta phải chọn ra trường hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đưa ra độ dài đó là đủ).

Về mặt cài đặt, dp sẽ được lưu trong mảng hai chiều. Kết quả của mảng này sẽ được tính toán thông qua vòng lặp hai lớp. Lưu ý rằng, chúng ta cần thực hiện vòng lặp sao cho chúng ta sẽ giải lần lượt từng bài toán con một, theo thứ tự từ nhỏ đến lớn. Bởi vì mỗi bài toán con dp(i, j) đều phụ thuộc vào các bài toán con trước đó dp(i – 1, j), dp(i, j – 1), dp(i – 1, j – 1).

n1, n2 = map(int, input().split())s1, s2 = input().split()t = * (len(s2) + 1) for _ in range(len(s1) + 1)>for i, x1 in enumerate(s1, 1): for j, x2 in enumerate(s2, 1): if x1 == x2: t = t + 1 else: t = max(t, t)print(t)# Kết quả khi giải các bài toán con như bảng sau:## S| t e z c a t l i p o c a# T ji| 0 1 2 3 4 5 6 7 8 9 10 11 12# —-+————————————–# 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0# q 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0# u 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0# e 3 | 0 0 1 1 1 1 1 1 1 1 1 1 1# t 4 | 0 1 1 1 1 1 2 2 2 2 2 2 2# z 5 | 0 1 1 2 2 2 2 2 2 2 2 2 2# a 6 | 0 1 1 2 2 3 3 3 3 3 3 3 3# l 7 | 0 1 1 2 2 3 3 4 4 4 4 4 4# c 8 | 0 1 1 2 3 3 3 4 4 4 4 5 5# o 9 | 0 1 1 2 3 3 3 4 4 4 5 5 5# a 10| 0 1 1 2 3 4 4 4 4 4 5 5 6# t 11| 0 1 1 2 3 4 5 5 5 5 5 5 6# l 12| 0 1 1 2 3 4 5 6 6 6 6 6 6Quy hoạch động vs. MemoizationCó một kỹ thuật khác gọi là “memoization” cũng có cách tiếp cận tương tự với quy hoạch động. Cả quy hoạch động và memoization đều dùng để tối ưu các vòng lặp mà có tính toán tượng tự nhau, trong đó kết quả của phép tính lớn hơn sẽ cần được tính toán dựa vào kết quả của phép tính nhỏ hơn. Memoization thường được sử dụng trong các phép tính đệ quy khi mà một tính toán bị lặp đi lặp lại nhiều lần. Nó sẽ lưu một bảng các giá trị tính được, mỗi khi có tính toán cần thực hiện, chúng ta sẽ tra bảng đó trước. Nếu bảng đã có kết quả rồi, chúng ta chỉ cần lấy ra là xong, nếu chưa, chúng ta sẽ tính toán như thường và tiếp tục lưu vào bảng.

Memoization không phải là một thuật toán theo đúng nghĩa, nó là một kỹ thuật được sử dụng trong lập trình thì đúng hơn. Để hiểu rõ hơn về kỹ thuật này, mình xin lấy ví dụ ngay với bài toán Fibonacci. Chúng ta sẽ sử dụng memoization như sau:

look_up = {0: 1, 1: 1}def fib(n): if look_up.get(n) is None: look_up = fib(n – 1) + fib(n – 2) return look_upSự khác biệt chủ yếu là quy hoạch động sẽ thực hiện việc tính toán theo một thứ tự định trước, trong khi memoization duyệt theo chiều sâu. Quy hoạch động không bao giờ tính toán một bài toán con hai lần, tương đối giống với các phép tính đệ quy với memoization. Tuy nhiên memoization thì không bao giờ tính toán những phép tính thừa trong khi quy hoạch động sẽ cần tất cả mọi bài toán con. Đây là một phương pháp khá hay, nó chỉ tính toán những gì cần thiết và lưu kết quả này lại để sau này dùng lại khi nào được gọi mà không cần tính toán nữa.

Dưới đây là một số ưu, nhược điểm của memoization khi so sánh với quy hoạch động:

Ưu điểm

Dễ code hơnKhông yêu cầu thứ tự thực hiện tính toánChỉ tính toán những gì cần thiết

Nhược điểm

Chỉ có một kiểu duyệt duy nhấtThường chậm hơn quy hoạch động.Các dạng toán quy hoạch động

Phần lớn các bài toán quy hoạch động có thể chia làm hai loại: bài toán cần quy hoạch động để tối ưu và bài toán quy tổ hợp. Trong những phần dưới đây, chúng ta sẽ xem xét từng loại bài toán này.

Bài toán tối ưu

Bài toán tối ưu yêu cầu chúng ta phải tìm đáp án tốt nhất từ mục tiêu của bài toán. Cả hai ví dụ mình đưa ra ở trên đều thuộc loại bài toán này (một bài tìm số đồng xu ít nhất, một bài tìm xâu con dài nhất). Mối liên hệ của các bài toán con thuộc dạng này có công thức chúng là dp = min(F1(dp, dp, …, dp), F2(dp, dp, …, dp), …, Fl(dp, dp

, …, dp)), trong đó dp mảng lưu kết quả của các bài toán con đó.

Xem thêm: Sửa Lỗi Không Format được Usb, 4 Cách đơn Giản Và Nhanh Nhất

Mỗi bài toán được giải dựa trên bài toán đã được giải trước đó. Đây chính là tính chất cấu trúc con tối ưu của mỗi bài toán. Với bài toán đồng xu, mỗi bài toán mới đều được giải bằng cách thêm đúng 1 đồng xu vào kết quả từ trước đó. Kết quả cuối cùng là kết quả tốt nhất thu được từ nhiều cách thêm đồng xu với khối lượng khác nhau.

Trước khi tính toán, mảng chứa kết quả có thể được điền đầy một giá trị trung tính nào đó. Giá trị trung tính có nghĩa là giá trị đó sẽ không bao giờ là đáp án cho bất kỳ bài toán con nào. Ví dụ khi cần tìm ra số đồng xu nhỏ nhất, chúng ta có thể điền mảng này bằng số dương lớn nhất, mọi tính toán tiếp theo sẽ cho ra một kết quả nhỏ hơn nhiều. Nếu không ra kết quả nào khác, chúng ta có thể coi như là không có một đáp án nào cho bài toán con đó.

Bài toán tổ hợp

Bài toán tổ hợp thường yêu cầu chúng ta tìm ra số cách khác nhau để thực hiện một việc gì đó. Nhiều bài thi code thường có kết quả rất lớn và họ yêu cầu chúng ta đưa đáp án dạng modulo của 10000007. Trong dạng bài toán này, công thức khi xây dựng các bài toán con sẽ là R = F1(R, R, …, R) + F2(R, R, …, R) + … + Fl(R, R

, …, R). Sự khác biệt cơ bản của dạng bài toán này với dạng bài toán tối ưu là ở chỗ chúng ta cần tính tổng thay vì tìm số lớn nhất hoặc nhỏ nhất.

Trong mọi bài toán quy hoạch động, tính chất cấu trúc con tối ưu luôn là quan trọng nhất và cũng là tính chất khó đảm bảo nhất. Nếu cấu trúc con không được tối ưu, chúng ta sẽ tính toán theo một phương thức sai lầm và đương nhiên, kết quả thu được cũng không chính xác.

Với phần lớn các bài toán quy hoạch động, việc chia các bài toán con gối nhau khá dễ dàng trong khi đảm bảo cấu trúc con tối ưu thì khó hơn nhiều.

Mình sẽ đưa ra hai ví dụ tương tự nhau cho các bạn hiểu rõ hơn về những khó khăn để đảm bảo tính chất này.

Vẫn với bài toán đồng xu, chúng ta sẽ thay đổi một chút để có bài toán tổ hợp như sau:

Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S.

Các bài toán con sẽ tương tự như trước: dp(P) = k là số cách khác nhau để chọn ra các đồng xu có tổng khối lượng là P. Công thức đệ quy trong trường hợp này sẽ biến đổi theo bài toán như sau:

# Công thức đệ quy cho bài toán quy hoạch động# {dp = 1;# {dp

= sum(dp); (for Wi ## Với đầu vào như sau: n = 3, S = 11, W = # Mảng kết quả quy hoạch động sẽ là# P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11# ——+–+–+–+–+–+–+–+–+–+–+–# k = 1 |1 |1 |2 |3 |5 |8 |12|19|30|47|74Bài toán tổ hợp cũng có thể có một giá trị trung tính. Bởi vì bài toán tổ hợp thường tính tổng, giá trị trung tính sẽ là 0. Bài toán tổ hợp yêu cầu tìm số cách khác nhau để làm gì đó, do đó giá trị 0 sẽ không ảnh hưởng gì đến đáp án. Một điểm đặc biệt quan trọng trong bài toán tổ hợp này là mỗi cách chúng ta chỉ tính đúng một lần. Nói thì dễ nhưng nhiều khi trong thực hành chúng ta hay gặp sai sót ở chỗ cực kỳ quan trọng này.

Tiếp tục thay đổi thêm một chút, chúng ta sẽ có bài toán tổ hợp như sau:

Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S. Với điều kiện, các cách lấy đồng xu là hoán vị của nhau không được coi là khác nhau.

Bài toán này khó hơn bài toán trước một chút. Nếu chúng vẫn chia các bài toán con như cũ thì không thể có được cấu trúc con tối ưu. Ví dụ, với các đồng xu 1, 3, 5 thì (1, 3) và (3, 1) đều cho kết quả là 4 nhưng chỉ được coi là 1 cách.

Với bài toán này, chúng ta sẽ chia bài toán lớn thành các bài toán con theo một cách tương đối khác. Chúng ta thấy rằng, kết quả (số cách chọn đồng xu) sẽ là tổng hợp của hai kết quả:

Số cách lấy đồng xu từ n – 1 đồng xu đầu tiên, tức là chúng ta coi như không có đồng xu nặng nhấtSố cách lấy đồng xu có chứa đồng xu nặng nhất.

Kết quả sẽ là tổng của hai kết quả trên. Các bạn thấy đó, với cách xây dựng bài toán con như thế này, chúng ta đã xây dựng các bài toán con gối nhau mà vẫn đảm bảo cấu trúc con tối ưu (kết quả bằng tổng của các bài toán con).

Nhân tiện, với cách chia bài toán như vậy, chúng ta có thể thu được lời giải bằng cách đệ quy đơn giản như sau:

n, S = map(int, input().split())w = list(map(int, input().split()))def count(arr, x): # Có 1 cách (lấy ra 0 đồng xu) cho tổng khối lượng bằng 0 if x == 0: return 1 # Không thể lấy được các đồng xu cho khối lượng âm if x 0: return 0 # Không thể lấy nếu không có đồng xu nào if not arr and x >= 1: return 0 # Kết quả là tổ hợp các bài toán con return count(arr, x) + count(arr, x – arr)print(count(w, S))Tuy nhiên, như mình đã nói ở phần trước, nếu bạn đang thi code, cách làm này sẽ không mang lại bất cứ hy vọng đạt giải nào, do nó cực kỳ mất thời gian và bộ nhớ. Tuy nhiên, chúng ta có thể áp dụng quy hoạch động cho bài toán này rất dễ dàng sau khi có được cấu trúc con tối ưu với các bài toán con gối nhau:

n, S = map(int, input().split())w = list(map(int, input().split()))dp = for _ in range(S + 1)>for i in range(n): dp = 1for i in range(1, S + 1): for j in range(n): x = dp> if i – w >= 0 else 0 y = dp if j >= 1 else 0 dp = x + yprint(dp)# Kết quả tính toán với n = 3, w = như sau:# S = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11# ——+–+–+–+–+–+–+–+–+–+–+–# k = 1 |1 |1 |2 |2 |3 |4 |4 |5 |6 |7 |8Các bạn thấy đó, xây dựng các bài toán con gối nhau sao cho cấu trúc con vẫn tối ưu nhiều khi không đơn giản chút nào. Và mỗi bài toán quy hoạch động lại có những biến hóa khác nhau mà không theo một khuôn mẫu khô cứng nào. Ngay cả khi bạn có thể giải được rất nhiều bài toán quy hoạch động rồi, không gì có thể đảm bảo bạn có thể giải được các bài khác nữa. Đó cũng là một lý do khiến cho dạng bài này luôn “hot” trong các cuộc thi.

Quy hoạch động xuôi và ngược

Tất cả những ví dụ mình đã trình bày ở trên đều sử dụng quy hoạch động kiểu “ngược”. Ngược ở đây không phải là chúng ta duyệt các bài toán con từ lớn ngược về nhỏ. Mà quy trình sẽ như thế này: Duyệt qua tất cả các bài toán con (từ nhỏ đến lớn), với mỗi bài toán đó, chúng ta tính toán kết quả dựa vào bài toán con trước đó. Tất nhiên, bài toán con phía trước đã được giải theo quy trình duyệt, và với mỗi bài toán, chúng ta phải “nhìn ngược lại” bài toán trước đó, nên cách làm này gọi là quy hoạch động kiểu “ngược”.

Phương pháp quy hoạch động ngược này được sử dụng rộng rãi, vì nó khá tương ứng với suy nghĩ tự nhiên của chúng ta. Chúng ta đọc đề bài, suy nghĩ cách giải cho nó. Cách giải đó yêu cầu phải giải những bài toán nhỏ hơn, như kiểu làm toán ngày phải chứng minh các bổ đề vậy. Chúng ta tiếp tục suy nghĩ cho những bài toán con này, rồi tổng hợp để tìm ra lời giải cho bài toán lớn. Quá trình cứ tiếp tục như vậy, và quy hoạch động kiểu “ngược” này đang được xây dựng đúng như vậy.

Ngoài ra, về mặt lập trình, kiểu quy hoạch động này có mối quan hệ tương đối gần gũi với đệ quy. Một bài toán lớn được giải dựa vào các bài toán con tương tự nhau (và tương tự bài toán lớn) thì việc áp dụng đệ quy có thể là một phương pháp dễ dàng để code. Vì vậy, nhiều trường hợp, có thể coi quy hoạch động là một cách để tối ưu phương pháp đệ quy để giải một bài toán.

Ngoài kiểu quy hoạch động ngược này, có một kiểu quy hoạch động “xuôi”. Tuy không phổ biến, kiểu quy hoạch động xuôi cũng khá khó áp dụng, nhưng quy hoạch động “xuôi” mang đến cho chúng ta nhiều tiện lợi. Kiểu xuôi này cũng cần duyệt qua các bài toán con từ nhỏ đến lớn, nhưng với mỗi bài toán con, chúng ta tính toán kết quả và từ đó tìm cách thực hiện một số phép tính để giải bài toán lớn hơn. Nghĩa là, với mỗi bài toán con, chúng ta sẽ nhìn về phía trước để xem phải giải bài toán tiếp theo như thế này từ bài toán hiện tại.

Phương pháp này khó áp dụng hơn phương pháp ngược kia, và cũng không phải bài toán nào cũng áp dụng được. Với mỗi bài toán, việc xác định bước tiếp theo tương đối khó khăn, thậm chí việc kiểm tra tính đúng sai của phương pháp cũng không hề dễ dàng.

Như chúng ta đã thấy ở những phần trước, thông thường, mỗi bài toán cần phải giải bằng cách tổng hợp kết quả từ một vài bài toán con trước đó. Vì vậy, cách quy hoạch động xuôi này chỉ sử dụng một bài toán con để tính toán trước bài toán tiếp theo sẽ chỉ cho ra một phần của kết quả chứ không phải kết quả cuối cùng. Vì vậy, để thực hiện quy hoạch động xuôi, việc điền sẵn một mảng các giá trị trung tính là điều bắt buộc (sau đó chúng ta sẽ cộng dồn kết quả vào mỗi khi giải được một bài toán con mới).

Mình lấy vị với bài toán xâu con chung dài nhất. Với bài toán này, chúng ta có thể chọn giá trị trung tính là một số âm. Chúng ta sẽ tìm cách quy hoạch động xuôi như sau:

dp(0,0) = 0 là bài toán với hai xâu rỗngVới mỗi bài toán dp(i, j) chúng ta sẽ tìm cách tính toán kết quả cho các bài toán lớn hơn. Lúc này, có 3 hướng phát triển tiếp:Lấy thêm một ký tự từ xâu thứ nhất => Kết quả không thay đổi.Lấy thêm một ký tự từ xâu thứ hai => Kết quả cũng không thay đổi.Nếu ký tự tiếp theo của cả hai xâu giống nhau => Lấy tự từ này và độ dài xâu con chung tăng lên 1.

Dưới đây là code cho bài toán này:

n1, n2 = map(int, input().split())s1, s2 = input().split()s1 += “