Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two-Dimensional DP

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Knapsack & Subset DP →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Longest Common Subsequence

Problem (restated)

Lengths of longest subsequence common to text1 and text2 (not necessarily contiguous).

Intuition

dp[i][j] = LCS of prefixes. Equal → +1 diagonal; else max(skip either).

Approaches

Classic LCS DP

Tested only
Time O(mn)Space O(min(m,n))

Idea. 1D rolling: dp[j] previous row; track prev diagonal carefully.

Walkthrough. abcde vs ace → 3.

Trade-offs. Edit distance is the same grid with different recurrences.

Solution
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]!;
}

Template connection

Two-dimensional DP on two strings.

Reflection