Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtwo-dimensional-dp

Longest Common Subsequence

Problem (yeniden ifade)

text1 ve text2’ye ortak en uzun altdizinin uzunluğu (bitişik olmak zorunda değil).

Sezgi

dp[i][j] = öneklerin LCS’i. Eşit → çapraz +1; değilse max(birini atla).

Yaklaşımlar

Klasik LCS DP

Doğrulanmadı

Zaman O(mn)Alan O(min(m,n))

Fikir. 1B kaydıran satır: dp[j] önceki satır; önceki çaprazı dikkatle izle.

Yürüyüş. abcde vs ace → 3.

Trade-off. Edit distance aynı ızgara, farklı yinelemeler.

Çözüm

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

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

Şablon bağlantısı

İki string üzerinde iki boyutlu DP.

Yansıma

Harfler eşitse çapraz artı 1, değilse max(üst, sol). İlk satır ve sütun 0.
Alt dizilim bitişik olmak zorunda değil; sıra korunur. Biri boşsa 0.
Aynı dizgi cevap uzunluk. Ortak harf yoksa 0.