Longest Common Subsequence (LCS) — độ dài dãy con chung dài nhất. Trình bày công thức DP 2 chiều?

Ý tưởng: dp[i][j] = độ dài LCS của text1[0..i) và text2[0..j). Quan hệ:
- Nếu text1[i-1] === text2[j-1]: ký tự khớp → dp[i][j] = dp[i-1][j-1] + 1.
- Ngược lại: bỏ một ký tự ở một trong hai → dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Hình dung: đối chiếu hai văn bản cột-hàng; gặp ký tự giống nhau thì đi chéo và cộng 1, khác thì lùi về phương án tốt hơn.

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = text1[i - 1] === text2[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1])
  return dp[m][n]
}

Độ phức tạp: thời gian O(m×n), bộ nhớ O(m×n) (có thể tối ưu xuống O(min(m,n)) bằng cuộn 2 hàng).

Lưu ý: "Subsequence" giữ thứ tự nhưng không cần liền kề — khác với "substring". LCS là nền cho diff/git, edit distance, longest palindromic subsequence.

Xem toàn bộ DSA cùng filter theo level & chủ đề con.

Mở danh sách DSA

Hình dung: đối chiếu hai văn bản cột-hàng; gặp ký tự giống nhau thì đi chéo và cộng 1, khác thì lùi về phương án tốt hơn.

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = text1[i - 1] === text2[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1])
  return dp[m][n]
}

Độ phức tạp: thời gian O(m×n), bộ nhớ O(m×n) (có thể tối ưu xuống O(min(m,n)) bằng cuộn 2 hàng).

Lưu ý: "Subsequence" giữ thứ tự nhưng không cần liền kề — khác với "substring". LCS là nền cho diff/git, edit distance, longest palindromic subsequence.