Edit Distance (Levenshtein) — số phép biến đổi tối thiểu giữa hai chuỗi. Ba phép insert/delete/replace ánh xạ vào DP thế nào?

Ý tưởng: dp[i][j] = số phép ít nhất biến word1[0..i) thành word2[0..j).
- Nếu ký tự khớp: dp[i][j] = dp[i-1][j-1] (không tốn phép).
- Nếu khác: 1 + min( dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace) ).

Biên: biến chuỗi rỗng thành chuỗi dài j cần đúng j phép insert → dp[0][j] = j, dp[i][0] = i.

function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length
  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)))
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = word1[i - 1] === word2[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
  return dp[m][n]
}

Độ phức tạp: thời gian O(m×n), bộ nhớ O(m×n) (có thể cuộn còn O(n)).

Lưu ý: Ba nhánh min chính là 3 phép — nhớ đúng ô nào ứng với phép nào (delete = bỏ 1 ký tự word1 = dp[i-1][j]). Đây là DP nền của spell-check và diff mờ.

Idea: dp[i][j] = fewest edits to turn word1[0..i) into word2[0..j).
- If characters match: dp[i][j] = dp[i-1][j-1] (free).
- If they differ: 1 + min( dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace) ).

Boundary: turning an empty string into a length-j string needs exactly j inserts → dp[0][j] = j, dp[i][0] = i.

function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length
  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)))
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = word1[i - 1] === word2[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
  return dp[m][n]
}

Complexity: time O(m×n), space O(m×n) (rollable to O(n)).

Note: The three min branches are the three operations — remember which cell maps to which (delete = drop 1 char of word1 = dp[i-1][j]). This DP underpins spell-check and fuzzy diff.