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.

Idea: dp[i][j] = LCS length of text1[0..i) and text2[0..j). Recurrence:
- If text1[i-1] === text2[j-1]: characters match → dp[i][j] = dp[i-1][j-1] + 1.
- Else: drop a char from one side → dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Picture it: aligning two texts in a grid; matching characters move diagonally and add 1, mismatches fall back to the better option.

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]
}

Complexity: time O(m×n), space O(m×n) (reducible to O(min(m,n)) by rolling two rows).

Note: A subsequence keeps order but is not contiguous — unlike a substring. LCS underpins diff/git, edit distance, and longest palindromic subsequence.