Patterns

dp[i][j] over two strings/arrays; compares chars at i, j

When to useLongest common subsequence, edit distance, longest palindromic subsequence

Delete String

delete_string

Combine String

combine_string

Dual-Sequence DP Introduction

dp_two_sequence_intro

Edit Distance

edit_distance · no slots

Longest Common Subsequence

longest_common_subsequence

Distinct Subsequences

distinct_subsequence

Shortest Common Supersequencehard

shortest_common_supersequence

DECLARE

dp = (m+1) × (n+1), filled with 0

—

const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));

const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

—

const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

const m = str1.length;
const n = str2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

BASE CASES

row 0 and column 0 default to 0

—

dp[0][0] = true;
for (let i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] && s1[i-1] === s3[i-1];
for (let j = 1; j <= n; j++) dp[0][j] = dp[0][j-1] && s2[j-1] === s3[j-1];

// row 0 and column 0 are 0 by fill — empty prefix has LCS length 0

—

// row 0 and column 0 are 0 by fill — empty prefix has LCS length 0

for (let i = 0; i <= m; i++) dp[i][0] = 1;
// dp[0][j] = 0 for j > 0 by fill — empty s can't form non-empty t

// row 0 and column 0 are 0 by fill — empty prefix has LCS length 0

BUILD

for i = 1..m, for j = 1..n

—

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {

—

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {

for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {

[RECURRENCE]

if s1[i-1] === s2[j-1] dp[i][j] = dp[i-1][j-1] + 1; else max/min

    if (s1[i - 1] === s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
    else dp[i][j] = Math.min(dp[i - 1][j] + costs[s1.charCodeAt(i - 1) - 97], dp[i][j - 1] + costs[s2.charCodeAt(j - 1) - 97]);

    dp[i][j] = (s1[i-1] === s3[i+j-1] && dp[i-1][j]) ||
               (s2[j-1] === s3[i+j-1] && dp[i][j-1]);

    if (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
    else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

—

    if (word1[i-1] === word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
    else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

    if (s[i-1] === t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    else dp[i][j] = dp[i-1][j];

    if (str1[i - 1] === str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

RETURN

return dp[m][n]

return dp[m][n];

return dp[m][n];

return dp[m][n];

—

return dp[m][n];

return dp[m][n];

// dp[m][n] is the LCS length; SCS length = m + n - dp[m][n].
// Reconstruction walks the table backwards — see solution.