DP hai chiều — LCS và Edit Distance: bảng dp[i][j] và truy vết

TL;DR: Longest Common Subsequence (LCS) và Edit Distance (Levenshtein) đều dùng bảng DP hai chiều dp[i][j] với state là "đã xử lý i ký tự đầu của chuỗi X và j ký tự đầu của chuỗi Y". Transition cho LCS: nếu X[i] == Y[j] thì dp[i][j] = dp[i-1][j-1] + 1, ngược lại max(dp[i-1][j], dp[i][j-1]). Transition cho Edit Distance: nếu ký tự khớp thì dp[i][j] = dp[i-1][j-1], ngược lại 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete/insert/replace). Truy vết ngược từ dp[m][n] về (0,0) để reconstruct chuỗi chung hoặc chuỗi thao tác.

Git hiển thị diff giữa hai file — dòng nào thêm, dòng nào xóa, dòng nào giữ nguyên. Spell-checker gợi ý "python" khi bạn gõ "pyhton". Cả hai bài toán này có cùng cấu trúc: so sánh hai chuỗi và đo sự tương đồng. DP 2D giải quyết chúng trong O(mn) — tối ưu về complexity và là nền tảng của diff, git merge, và autocorrect trong mọi editor.

Bài này xây trên DP Framework và DP 1D — cùng tư duy 5 bước nhưng state nay là hai chiều (i, j).

1. Analogy — So sánh hai bài văn

Hãy tưởng tượng hai giáo viên cùng chấm bài: một người đọc bài của học sinh A theo từng câu, người kia đọc bài của học sinh B. Họ ngồi cạnh nhau và ghi vào bảng: "đến đây, câu 3 của A và câu 2 của B — hai bài giống nhau được bao nhiêu phần?"

dp[i][j] chính là ô trong bảng đó: "đã xét i ký tự đầu của A và j ký tự đầu của B — kết quả tốt nhất là gì?"

2. Longest Common Subsequence (LCS)

2.1 Định nghĩa

Subsequence (dãy con) của chuỗi X là chuỗi thu được từ X bằng cách xóa một số ký tự (không cần liên tiếp) mà giữ nguyên thứ tự. Khác với substring — substring phải liên tiếp.

Ví dụ: X = "ABCDE". Subsequence hợp lệ: "ACE", "BD", "ABCDE", "". Substring hợp lệ: "ABC", "BCD", "DE".

LCS (Longest Common Subsequence): chuỗi con dài nhất xuất hiện trong cả hai chuỗi X và Y (dưới dạng subsequence, không cần liên tiếp).

Ví dụ: X = "AGGTAB", Y = "GXTXAYB" → LCS = "GTAB" (độ dài 4).

2.2 State và transition

State: dp[i][j] = độ dài LCS của X[1..i] (i ký tự đầu của X) và Y[1..j] (j ký tự đầu của Y).

Transition (1-indexed):

if X[i] = Y[j]:
    dp[i][j] <- dp[i-1][j-1] + 1     -- ký tự khớp, kéo dài LCS
else:
    dp[i][j] <- max(dp[i-1][j], dp[i][j-1])
    -- bỏ X[i] (nhìn lên) hoặc bỏ Y[j] (nhìn trái)

Giải thích transition:

• Nếu X[i] == Y[j]: cả hai ký tự này có thể "khớp" nhau trong LCS, kéo dài LCS của hai prefix ngắn hơn thêm 1.
• Nếu X[i] != Y[j]: ít nhất một trong hai ký tự không nằm trong LCS. Thử bỏ X[i] (giải bài dp[i-1][j]) hoặc bỏ Y[j] (giải bài dp[i][j-1]), lấy kết quả tốt hơn.

Base case: dp[0][j] = 0 và dp[i][0] = 0 — LCS với chuỗi rỗng luôn = 0.

2.3 Pseudocode

LCS_length(X, Y, m, n):
    -- X có m ký tự, Y có n ký tự (1-indexed)
    dp[i][j] <- 0 cho mọi i, j    -- base case bao gồm hàng 0 và cột 0

    for i <- 1 đến m:
        for j <- 1 đến n:
            if X[i] = Y[j]:
                dp[i][j] <- dp[i-1][j-1] + 1
            else:
                dp[i][j] <- max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Time: O(mn) Space: O(mn), tối ưu xuống O(n) nếu không cần truy vết

2.4 Trace bảng — X = "ABCB", Y = "BDCAB"

Bảng dp[i][j], hàng 0 và cột 0 là 0 (base case):

dp[4][5] = 3 → LCS có độ dài 3. Truy vết (xem mục 2.5) cho ra "BCB".

Kiểm tra một ô: dp[2][1] — X[2]="B", Y[1]="B" → khớp → dp[1][0] + 1 = 0 + 1 = 1. Đúng.

dp[3][3] — X[3]="C", Y[3]="C" → khớp → dp[2][2] + 1 = 1 + 1 = 2. Đúng.

2.5 Truy vết — reconstruct LCS thực tế

dp[m][n] cho biết độ dài LCS, nhưng chưa cho biết LCS là chuỗi gì. Để reconstruct, đi ngược từ (m, n) về (0, 0):

reconstruct_LCS(X, Y, dp, m, n):
    result <- []
    i <- m,  j <- n

    while i > 0 and j > 0:
        if X[i] = Y[j]:
            result.prepend(X[i])    -- ký tự này nằm trong LCS
            i <- i - 1
            j <- j - 1
        else if dp[i-1][j] >= dp[i][j-1]:
            i <- i - 1              -- đến từ ô trên → bỏ X[i]
        else:
            j <- j - 1              -- đến từ ô trái → bỏ Y[j]

    return result

Time: O(m+n) Space: O(m+n) cho kết quả

Trace truy vết bảng trên:

Kết quả (đã prepend theo thứ tự bước 5→3→1): "B" → "CB" → "BCB". LCS = "BCB", độ dài 3.

Thử ngẫmhai đồng nghiệp chạy git diff trên cùng file, một người thấy dòng X bị xoá rồi thêm lại, người kia thấy dòng X được giữ nguyên. LCS không unique giải thích được gì ở đây?

3. Edit Distance (Levenshtein Distance)

3.1 Định nghĩa

Edit Distance giữa hai chuỗi X và Y là số thao tác tối thiểu để biến X thành Y. Có ba thao tác, mỗi thao tác cost 1:

• Insert: chèn 1 ký tự vào X.
• Delete: xóa 1 ký tự khỏi X.
• Replace: thay thế 1 ký tự trong X bằng ký tự khác.

Ví dụ: X = "kitten", Y = "sitting" → Edit Distance = 3.

• kitten → sitten (replace k→s)
• sitten → sittin (replace e→i)
• sittin → sitting (insert g)

3.2 State và transition

State: dp[i][j] = edit distance giữa X[1..i] và Y[1..j].

Transition (1-indexed):

if X[i] = Y[j]:
    dp[i][j] <- dp[i-1][j-1]         -- ký tự khớp, không cần thao tác
else:
    dp[i][j] <- 1 + min(
        dp[i-1][j],                   -- delete X[i]
        dp[i][j-1],                   -- insert Y[j] vào X
        dp[i-1][j-1]                  -- replace X[i] bằng Y[j]
    )

Giải thích ba thao tác:

• dp[i-1][j] + 1: xóa X[i] — cần edit distance từ X[1..i-1] sang Y[1..j], rồi thêm 1 thao tác delete.
• dp[i][j-1] + 1: chèn Y[j] vào X — cần edit distance từ X[1..i] sang Y[1..j-1], rồi thêm 1 thao tác insert.
• dp[i-1][j-1] + 1: thay X[i] bằng Y[j] — cần edit distance từ X[1..i-1] sang Y[1..j-1], rồi thêm 1 thao tác replace.

Base case:

• dp[i][0] = i — biến X[1..i] thành chuỗi rỗng: cần i lần delete.
• dp[0][j] = j — biến chuỗi rỗng thành Y[1..j]: cần j lần insert.

3.3 Pseudocode

edit_distance(X, Y, m, n):
    -- base case: hàng 0 và cột 0
    dp[i][0] <- i  cho mọi i từ 0 đến m
    dp[0][j] <- j  cho mọi j từ 0 đến n

    for i <- 1 đến m:
        for j <- 1 đến n:
            if X[i] = Y[j]:
                dp[i][j] <- dp[i-1][j-1]
            else:
                dp[i][j] <- 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

    return dp[m][n]

Time: O(mn) Space: O(mn), tối ưu xuống O(n) nếu không cần truy vết

3.4 Trace bảng — X = "CAT", Y = "CUT"

Base case: hàng 0 = [0,1,2,3], cột 0 = [0,1,2,3].

dp[3][3] = 1 → chỉ cần 1 thao tác: thay 'A' bằng 'U'.

Kiểm tra ô dp[2][2]: X[2]="A", Y[2]="U" → không khớp → 1 + min(dp[1][2], dp[2][1], dp[1][1]) = 1 + min(1, 1, 0) = 1. Đúng (thay C→C rồi A→U chỉ cần 1 replace).

Ba ô lân cận không phải ba ô bất kỳ: mỗi hướng đi là một phép edit cụ thể, và đó là lý do transition có đúng ba nhánh chứ không phải hai hay bốn. Hình cũng vẽ đủ hàng ε và cột ε — nhìn thấy hàng đầu chạy 0-1-2-3 thì lý do base case là i và j chứ không phải 0 tự hiện ra: biến chuỗi rỗng thành "CUT" cần đúng 3 lần chèn.

3.5 Truy vết — reconstruct chuỗi thao tác

reconstruct_edits(X, Y, dp, m, n):
    ops <- []
    i <- m,  j <- n

    while i > 0 or j > 0:
        if i > 0 and j > 0 and X[i] = Y[j]:
            ops.prepend("match " + X[i])
            i <- i - 1
            j <- j - 1
        else if i > 0 and j > 0 and dp[i][j] = dp[i-1][j-1] + 1:
            ops.prepend("replace " + X[i] + " → " + Y[j])
            i <- i - 1
            j <- j - 1
        else if i > 0 and dp[i][j] = dp[i-1][j] + 1:
            ops.prepend("delete " + X[i])
            i <- i - 1
        else:
            ops.prepend("insert " + Y[j])
            j <- j - 1

    return ops

Time: O(m+n) Space: O(m+n)

Trace "CAT" → "CUT" từ dp[3][3]=1:

Chuỗi thao tác (đã prepend): match C, replace A→U, match T. Đúng — chỉ 1 thao tác replace.

Thử ngẫmnếu bàn phím tiếng Việt gõ nhầm dấu ("ă" thành "a"), thao tác "thay dấu" có nên tính cost bằng 1 như insert/delete/replace thường, hay cần trọng số khác?

4. Tối ưu space

4.1 Từ O(mn) xuống O(n)

Transition DP 2D chỉ cần hàng hiện tại và hàng trên → giữ 2 hàng thay toàn bộ bảng:

LCS_optimized(X, Y, m, n):
    prev <- [0, 0, ..., 0]  -- hàng i-1 (n+1 phần tử)
    curr <- [0, 0, ..., 0]  -- hàng i

    for i <- 1 đến m:
        curr[0] <- 0         -- base case cột 0
        for j <- 1 đến n:
            if X[i] = Y[j]:
                curr[j] <- prev[j-1] + 1
            else:
                curr[j] <- max(prev[j], curr[j-1])
        prev <- copy(curr)   -- chuẩn bị cho vòng lặp tiếp theo

    return prev[n]

Time: O(mn) Space: O(n)

4.2 Đánh đổi: tối ưu space thì mất khả năng truy vết

Khi chỉ giữ 2 hàng, không thể trace ngược để reconstruct LCS hay chuỗi thao tác. Phải chọn:

• Cần chỉ độ dài/khoảng cách: tối ưu space O(n).
• Cần reconstruct path: giữ toàn bộ bảng O(mn) hoặc dùng Hirschberg's algorithm (O(mn) time, O(n) space, có thể reconstruct — advanced).

5. Ứng dụng thực tế

5.1 git diff và diff tool

git diff dùng thuật toán Myers diff (1986) — về bản chất là biến thể tối ưu của LCS. Hai file là hai chuỗi dòng; LCS của chúng là tập dòng giữ nguyên. Dòng không nằm trong LCS: nếu chỉ trong file cũ → dòng xóa (hiện đỏ -), chỉ trong file mới → dòng thêm (hiện xanh +).

Complexity của Myers diff: O(n·d) với d là số dòng thay đổi — tốt hơn O(mn) khi diff nhỏ (file lớn nhưng ít thay đổi).

5.2 Spell-checker và autocorrect

Spell-checker tính edit distance từ từ sai sang mọi từ trong từ điển, gợi ý từ có edit distance nhỏ nhất. "pyhton" → "python" (1 swap), "teh" → "the" (1 swap). Với edit distance mở rộng (Damerau-Levenshtein: thêm phép transposition — hoán vị 2 ký tự liền nhau), "adn" → "and" chỉ cần 1 thao tác thay vì 2.

Thực tế production dùng BK-tree (Burkhard-Keller tree) để không phải so sánh với toàn bộ từ điển: query trong O(log N) thay vì O(N).

5.3 DNA sequence alignment

Bioinformatics dùng edit distance để so sánh chuỗi DNA/protein. Smith-Waterman (local alignment) và Needleman-Wunsch (global alignment) là biến thể của edit distance với scoring matrix (match/mismatch/gap penalty khác nhau thay vì cost cố định = 1).

Thử ngẫmmột pipeline phân tích DNA cần so hai chuỗi dài hàng triệu ký tự nhưng RAM giới hạn. Tối ưu space O(n) có đủ, hay cần thuật toán khác để vừa tiết kiệm vừa truy vết được?

6. Pitfall

Pitfall 1 — Nhầm 1-indexed và 0-indexed trong transition

-- BUG: code dùng 0-indexed nhưng transition viết theo 1-indexed
-- X[0..m-1], Y[0..n-1] nhưng vòng lặp dùng i từ 1 đến m
-- Khi đọc X[i], thực ra đọc X[1] = ký tự thứ 2 (0-indexed off-by-one)
for i <- 1 đến m:
    for j <- 1 đến n:
        if X[i] = Y[j]:   -- X[i] là ký tự thứ 2 nếu 0-indexed!

-- CORRECT: nhất quán về indexing
-- Cách 1: chuỗi 1-indexed (thêm sentinel ở index 0)
X <- " " + X_original   -- X[1..m] là ký tự thực

-- Cách 2: chuỗi 0-indexed, vòng lặp điều chỉnh
for i <- 1 đến m:
    for j <- 1 đến n:
        if X[i-1] = Y[j-1]:   -- X[i-1] = ký tự thứ i (0-indexed)

Pitfall 2 — Quên base case cho hàng 0 và cột 0 của Edit Distance

-- BUG: quên khởi tạo dp[i][0] và dp[0][j]
dp[i][j] <- 0 cho mọi i, j   -- sai! edit distance với chuỗi rỗng != 0

-- CORRECT:
dp[i][0] <- i  cho mọi i   -- xóa i lần để biến X[1..i] thành rỗng
dp[0][j] <- j  cho mọi j   -- chèn j lần để biến rỗng thành Y[1..j]

Không khởi tạo đúng cột/hàng 0 → toàn bộ bảng sai vì mọi ô phụ thuộc base case.

Pitfall 3 — Truy vết: tie-breaking sai dẫn đến LCS khác

-- Khi dp[i-1][j] = dp[i][j-1] trong LCS, có thể đi theo hướng nào cũng cho
-- một LCS hợp lệ — nhưng hai hướng cho LCS khác nhau.
-- Đây KHÔNG phải bug — LCS không unique.

-- Ví dụ: X = "ABCB", Y = "BCAB"
-- Hai LCS đều hợp lệ: "BCB" và "BAB" hoặc "CAB"...
-- Nếu test so sánh exact string sẽ fail khi tie-breaking khác nhau.
-- CORRECT: khi test LCS, kiểm tra độ dài, không kiểm tra exact string.

7. Liên hệ các bài khác

• DP Framework: Bài này áp dụng cùng quy trình 5 bước — state, transition, base case, thứ tự, tối ưu space — lên state 2 chiều.
• DP 1D: DP 1D là trường hợp đặc biệt khi chuỗi thứ hai có 1 chiều. Cùng tư duy transition, chỉ bảng dp từ mảng 1D lên 2D.
• Knapsack: Bài toán state 2D khác: dp[item][capacity]. Transition khác (chọn/bỏ item) nhưng cùng cấu trúc bảng 2D và tối ưu space O(capacity).
• Amortized analysis: LCS O(mn) — mỗi ô dp tính O(1), điền đủ mn ô. Amortized O(1) per ô, tổng O(mn). Cùng tư duy phân tích tổng chi phí.
• Recursion và call stack: Memoization cho LCS 2D cần đệ quy 2 tham số — call stack 2D thay vì 1D. Bottom-up (tabulation) tránh vấn đề này.

📚 Deep Dive

Tóm tắt

• LCS: dp[i][j] = độ dài LCS của X[1..i] và Y[1..j]. Nếu X[i]==Y[j] thì dp[i-1][j-1]+1; ngược lại max(dp[i-1][j], dp[i][j-1]). Base case = 0.
• Edit Distance: dp[i][j] = số thao tác tối thiểu. Nếu khớp: dp[i-1][j-1]; không khớp: 1 + min(delete, insert, replace). Base case hàng/cột 0 = i/j.
• Thứ tự điền bảng: từ (1,1) đến (m,n) — hàng trên và cột trái phải có trước.
• Truy vết: đi ngược từ (m,n) về (0,0) theo hướng ô kế trước trong transition.
• Tối ưu space: O(mn) → O(n) bằng cách giữ 2 hàng, nhưng mất khả năng reconstruct.
• Ứng dụng: git diff (LCS dòng), spell-checker (edit distance), DNA alignment (biến thể scoring).

Tự kiểm tra

Bài tiếp theo: Knapsack 0/1 và Unbounded Knapsack