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.

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).

flowchart TD
    INIT["Khởi tạo:<br/>dp[i][0] = i, dp[0][j] = j"]
    LOOP["Vòng lặp i=1..m, j=1..n"]
    MATCH{"X[i] = Y[j]?"}
    COPY["dp[i][j] = dp[i-1][j-1]<br/>(ký tự khớp, không thao tác)"]
    EDIT["dp[i][j] = 1 + min(<br/>dp[i-1][j],  ← xóa<br/>dp[i][j-1],  ← chèn<br/>dp[i-1][j-1] ← thay)"]
    DONE["Trả về dp[m][n]"]

    INIT --> LOOP
    LOOP --> MATCH
    MATCH -- "có" --> COPY
    MATCH -- "không" --> EDIT
    COPY --> LOOP
    EDIT --> LOOP
    LOOP -- "xong" --> DONE

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.

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).

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