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". LCS lấy dp[i-1][j-1] + 1 khi ký tự khớp, ngược lại max của ô trên và ô trái. Edit Distance lấy dp[i-1][j-1] khi khớp, ngược lại 1 + min của ba ô lân cận (delete/insert/replace). Truy vết ngược từ dp[m][n] về (0,0) để dựng lại 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ó chung cấu trúc: so sánh hai chuỗi và đo độ giống nhau. DP 2D giải cả hai trong O(mn), 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: vẫn quy trình 5 bước, state giờ có hai chiều (i, j).

1. Hình dung: so sánh hai bài văn

Hình dung hai giáo viên cùng chấm bài, ghi vào bảng: "đến câu i của A và câu j của B, hai bài giống nhau được bao nhiêu phần?"