2-Dimensional Dynamic Programming (2DP) is used when the answer depends on two changing states.

Its core advantage:

Break a problem into smaller states dp[i][j] and build the answer from previously solved states.

Focus on recognizing:

“Two positions / two sequences / grid / range” = 2D DP

Pattern Table

Pattern	Typical Questions	Trigger
Grid DP	Unique Paths, Min Path Sum	`dp[row][col]`
0/1 Knapsack	Max value with capacity	Take / Skip
Unbounded Knapsack	Coin Change, Rod Cutting	Reuse items
LCS	Common subsequence	Two sequences
Longest Common Substring	Common continuous part	Matching characters
Edit Distance	Convert one string to another	Insert / Delete / Replace
Distinct Subsequences	Count ways to form target	Match / Skip
Palindrome DP	Palindrome problems	`dp[i][j]` range
Interval DP	Burst Balloons, MCM	Solve `[i...j]`
Partition DP	Split into segments	Try every cut

Mental Trigger

Two changing variables → dp[i][j] → Define the state → Find the transition.

1. Grid DP

Use Grid DP when the problem asks about paths, movement, or optimization inside a matrix.

Common Problems

Unique Paths
Minimum Path Sum
Dungeon Game
Grid traversal problems

Mental Trigger

“Grid + move from one cell to another” → Grid DP.

Base Template: Count Paths

Every cell = “ways to reach here” — only from top and left. Watch the table fill row by row:

Unique Paths

Count paths from top-left to bottom-right moving only down/right.

Base: one way along the top row and left column. Every other cell dp[r][c] = dp[r−1][c] + dp[r][c−1] (came from above or left). O(rows·cols) time and space; one row suffices with care.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0][c] = 1, dp[r][0] = 1
                      
                        2
                        for r from 1..rows-1:
                      
                        3
                          for c from 1..cols-1:
                      
                        4
                            dp[r][c] = dp[r-1][c] + dp[r][c-1]
                      
                        5
                        return dp[rows-1][cols-1]

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++)
        dp[i][0] = 1;

    for (int j = 0; j < n; j++)
        dp[0][j] = 1;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        dp[i][0] = 1

    for j in range(n):
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n));

    for (int i = 0; i < m; i++)
        dp[i][0] = 1;

    for (int j = 0; j < n; j++)
        dp[0][j] = 1;

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

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

  for (let i = 0; i < m; i++)
    dp[i][0] = 1;

  for (let j = 0; j < n; j++)
    dp[0][j] = 1;

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}

What Does `dp[i][j]` Mean?

dp[i][j] = number of ways to reach cell (i, j)

Transition

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

Because we can reach the current cell from:

     top
      ↓
left → current

Pattern 1.1: Minimum Path Sum

Java Code

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;

    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] =
                grid[i][j] +
                Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

def min_path_sum(grid):
    m = len(grid)
    n = len(grid[0])

    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]

    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = (
                grid[i][j]
                + min(dp[i - 1][j], dp[i][j - 1])
            )

    return dp[m - 1][n - 1]

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    vector<vector<int>> dp(m, vector<int>(n));

    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] =
                grid[i][j] +
                min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m - 1][n - 1];
}

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;

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

  dp[0][0] = grid[0][0];

  for (let i = 1; i < m; i++)
    dp[i][0] = dp[i - 1][0] + grid[i][0];

  for (let j = 1; j < n; j++)
    dp[0][j] = dp[0][j - 1] + grid[0][j];

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] =
        grid[i][j] +
        Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }

  return dp[m - 1][n - 1];
}

What Changed from Base?

Base:

dp[i][j] = top + left;

Changed:

dp[i][j] = grid[i][j] + Math.min(top, left);

because now we want the minimum cost, not the number of paths.

Grid DP = Look at neighboring cells → combine their answers.

2. 0/1 Knapsack

Each item is take-it-or-leave-it. The table fills capacity across, items down:

0/1 Knapsack

Max value fitting in a capacity, each item used at most once.

dp[i][c] = best value using first i items at capacity c. If the item fits, take max(leave it: dp[i−1][c], take it: dp[i−1][c−w]+v). The table makes every take/skip trade-off explicit; O(items·capacity).

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][c] = best value with items 0..i-1 and capacity c
                      
                        2
                        if w[i] > c: dp[i][c] = dp[i-1][c]
                      
                        3
                        else: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
                      
                        4
                        return dp[n][capacity]

Use when every item can be used at most once.

Common Problems

0/1 Knapsack
Partition Equal Subset Sum
Target Sum variations
Subset Sum

Mental Trigger

“Take or skip each item once” → 0/1 Knapsack.

Base Template

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        int weight = weights[i - 1];
        int value = values[i - 1];

        for (int cap = 0; cap <= capacity; cap++) {

            // Skip item
            dp[i][cap] = dp[i - 1][cap];

            // Take item
            if (weight <= cap) {
                dp[i][cap] = Math.max(
                    dp[i][cap],
                    value + dp[i - 1][cap - weight]
                );
            }
        }
    }

    return dp[n][capacity];
}

def knapsack(weights, values, capacity):
    n = len(weights)

    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for cap in range(capacity + 1):
            # Skip item
            dp[i][cap] = dp[i - 1][cap]

            # Take item
            if weight <= cap:
                dp[i][cap] = max(
                    dp[i][cap],
                    value + dp[i - 1][cap - weight]
                )

    return dp[n][capacity]

int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();

    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1));

    for (int i = 1; i <= n; i++) {
        int weight = weights[i - 1];
        int value = values[i - 1];

        for (int cap = 0; cap <= capacity; cap++) {

            // Skip item
            dp[i][cap] = dp[i - 1][cap];

            // Take item
            if (weight <= cap) {
                dp[i][cap] = max(
                    dp[i][cap],
                    value + dp[i - 1][cap - weight]
                );
            }
        }
    }

    return dp[n][capacity];
}

function knapsack(weights, values, capacity) {
  const n = weights.length;

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

  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1];
    const value = values[i - 1];

    for (let cap = 0; cap <= capacity; cap++) {
      // Skip item
      dp[i][cap] = dp[i - 1][cap];

      // Take item
      if (weight <= cap) {
        dp[i][cap] = Math.max(
          dp[i][cap],
          value + dp[i - 1][cap - weight]
        );
      }
    }
  }

  return dp[n][capacity];
}

What Does `dp[i][cap]` Mean?

dp[i][cap] = maximum value using first i items
             with capacity cap

Two Choices

Skip → dp[i - 1][cap]

Take → value + dp[i - 1][cap - weight]

0/1 Knapsack = Take or Skip + Item used once.

3. Unbounded Knapsack

Use when an item can be used multiple times.

Common Problems

Coin Change
Rod Cutting
Unbounded Knapsack
Combination Sum

Mental Trigger

“Unlimited reuse” → Unbounded Knapsack.

Base Template

Unbounded Knapsack

Pick items with unlimited reuse to maximize value within capacity.

Unlike 0/1, when we TAKE an item we stay in the same row (dp[i][cap - weight]) so the item can be reused. dp[i][cap] = max(dp[i-1][cap], value + dp[i][cap-weight]). O(n·capacity) time, O(capacity) rolling space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = 0
                      
                        2
                        for i in 1..n:
                      
                        3
                          for cap in 0..capacity:
                      
                        4
                            dp[i][cap] = max(dp[i-1][cap], value[i] + dp[i][cap-weight[i]])
                      
                        5
                        return dp[n][capacity]

public int unboundedKnapsack(
        int[] weights,
        int[] values,
        int capacity) {

    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        int weight = weights[i - 1];
        int value = values[i - 1];

        for (int cap = 0; cap <= capacity; cap++) {

            // Skip
            dp[i][cap] = dp[i - 1][cap];

            // Take again
            if (weight <= cap) {
                dp[i][cap] = Math.max(
                    dp[i][cap],
                    value + dp[i][cap - weight]
                );
            }
        }
    }

    return dp[n][capacity];
}

def unbounded_knapsack(weights, values, capacity):
    n = len(weights)

    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for cap in range(capacity + 1):
            # Skip
            dp[i][cap] = dp[i - 1][cap]

            # Take again
            if weight <= cap:
                dp[i][cap] = max(
                    dp[i][cap],
                    value + dp[i][cap - weight]
                )

    return dp[n][capacity]

int unboundedKnapsack(vector<int>& weights,
                      vector<int>& values,
                      int capacity) {
    int n = weights.size();

    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1));

    for (int i = 1; i <= n; i++) {
        int weight = weights[i - 1];
        int value = values[i - 1];

        for (int cap = 0; cap <= capacity; cap++) {

            // Skip
            dp[i][cap] = dp[i - 1][cap];

            // Take again
            if (weight <= cap) {
                dp[i][cap] = max(
                    dp[i][cap],
                    value + dp[i][cap - weight]
                );
            }
        }
    }

    return dp[n][capacity];
}

function unboundedKnapsack(weights, values, capacity) {
  const n = weights.length;

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

  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1];
    const value = values[i - 1];

    for (let cap = 0; cap <= capacity; cap++) {
      // Skip
      dp[i][cap] = dp[i - 1][cap];

      // Take again
      if (weight <= cap) {
        dp[i][cap] = Math.max(
          dp[i][cap],
          value + dp[i][cap - weight]
        );
      }
    }
  }

  return dp[n][capacity];
}

What Changed from 0/1 Knapsack?

0/1:

dp[i - 1][cap - weight]

Unbounded:

dp[i][cap - weight]

The important difference is:

i - 1 → item cannot be reused

i     → item can be used again

Unbounded Knapsack = Same item can be taken again.

4. Longest Common Subsequence (LCS)

Two strings, one table — cells compare letters and inherit from the best neighbour:

Longest Common Subsequence

Length of the longest subsequence shared by two strings.

dp[i][j] over prefixes. If s1[i]==s2[j] take the diagonal +1; else inherit max(up, left). Matches trace diagonals, mismatches take the better neighbour. O(n·m) time and space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
                      
                        2
                        if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
                      
                        3
                        else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                      
                        4
                        return dp[n][m]

Use when comparing two strings/sequences and characters must remain in order, but can be skipped.

Common Problems

Longest Common Subsequence
Delete Operation for Two Strings
Minimum Insertions/Deletions

Mental Trigger

“Two sequences + common + order preserved” → LCS.

Base Template

public int longestCommonSubsequence(String a, String b) {
    int m = a.length();
    int n = b.length();

    int[][] dp = new int[m + 1][n + 1];

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

            if (a.charAt(i - 1) == b.charAt(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 dp[m][n];
}

def longest_common_subsequence(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):

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

    return dp[m][n]

int longestCommonSubsequence(string& a, string& b) {
    int m = a.size();
    int n = b.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

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

    return dp[m][n];
}

function longestCommonSubsequence(a, b) {
  const m = a.length;
  const n = b.length;

  const dp = 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++) {
      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]);
      }
    }
  }

  return dp[m][n];
}

What Does `dp[i][j]` Mean?

LCS of first i characters of a
and first j characters of b

Transition

If characters match:

dp[i][j] = dp[i - 1][j - 1] + 1;

If they don’t:

dp[i][j] = Math.max(
    dp[i - 1][j],
    dp[i][j - 1]
);

Match → diagonal + 1. Don’t match → skip one side.

5. Longest Common Substring

Use when the common part must be continuous.

Mental Trigger

“Two strings + continuous matching” → Longest Common Substring.

Longest Common Substring

Longest contiguous run common to both strings.

dp[i][j] = length of common substring ending at a[i-1] and b[j-1]. If chars match: dp[i][j] = dp[i-1][j-1] + 1; else 0 (match must stay continuous). Track the max cell.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp = 0-filled (m+1) x (n+1)
                      
                        2
                        best = 0
                      
                        3
                        for i in 1..m:
                      
                        4
                          for j in 1..n:
                      
                        5
                            if a[i-1] == b[j-1]:
                      
                        6
                              dp[i][j] = dp[i-1][j-1] + 1
                      
                        7
                              best = max(best, dp[i][j])
                      
                        8
                        return best

Java Template

public int longestCommonSubstring(String a, String b) {
    int m = a.length();
    int n = b.length();

    int[][] dp = new int[m + 1][n + 1];
    int best = 0;

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

            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                best = Math.max(best, dp[i][j]);
            }
        }
    }

    return best;
}

def longest_common_substring(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])

    return best

int longestCommonSubstring(string& a, string& b) {
    int m = a.size();
    int n = b.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    int best = 0;

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

            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                best = max(best, dp[i][j]);
            }
        }
    }

    return best;
}

function longestCommonSubstring(a, b) {
  const m = a.length;
  const n = b.length;

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

  let best = 0;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        best = Math.max(best, dp[i][j]);
      }
    }
  }

  return best;
}

What Changed from LCS?

LCS mismatch:

Math.max(dp[i - 1][j], dp[i][j - 1])

Substring mismatch:

dp[i][j] = 0;

because the match must remain continuous.

LCS can skip. Substring cannot skip.

6. Edit Distance

Edit Distance

Minimum insert/delete/replace ops to turn one string into another.

dp[i][j] = ops for first i of s1, first j of s2. Match → dp[i-1][j-1]; else 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]). The table fills by comparing characters cell by cell. O(n·m) time and space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][j] = min ops to convert s1[0..i-1] to s2[0..j-1]
                      
                        2
                        if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
                      
                        3
                        else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                      
                        4
                        return dp[n][m]

Use when converting one string into another using:

Insert
Delete
Replace

Mental Trigger

“Convert string A → string B” → Edit Distance.

Java Template

public int minDistance(String a, String b) {
    int m = a.length();
    int n = b.length();

    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++)
        dp[i][0] = i;

    for (int j = 0; j <= n; j++)
        dp[0][j] = j;

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

            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],           // delete
                    Math.min(
                        dp[i][j - 1],       // insert
                        dp[i - 1][j - 1]    // replace
                    )
                );
            }
        }
    }

    return dp[m][n];
}

def min_distance(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i

    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):

            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                    dp[i - 1][j - 1]   # replace
                )

    return dp[m][n]

int minDistance(string& a, string& b) {
    int m = a.size();
    int n = b.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; i++)
        dp[i][0] = i;

    for (int j = 0; j <= n; j++)
        dp[0][j] = j;

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

            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(
                    dp[i - 1][j],           // delete
                    min(
                        dp[i][j - 1],       // insert
                        dp[i - 1][j - 1]    // replace
                    )
                );
            }
        }
    }

    return dp[m][n];
}

function minDistance(a, b) {
  const m = a.length;
  const n = b.length;

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

  for (let i = 0; i <= m; i++)
    dp[i][0] = i;

  for (let j = 0; j <= n; j++)
    dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] =
          1 +
          Math.min(
            dp[i - 1][j],      // delete
            dp[i][j - 1],      // insert
            dp[i - 1][j - 1]   // replace
          );
      }
    }
  }

  return dp[m][n];
}

What Does `dp[i][j]` Mean?

Minimum operations to convert
first i characters of a
into first j characters of b

Match → diagonal. Mismatch → insert / delete / replace.

7. Distinct Subsequences

Distinct Subsequences

Count ways to form target t from source s as a subsequence.

dp[i][j] = ways to build t[0..j-1] using s[0..i-1]. If s[i-1]==t[j-1]: dp[i][j] = dp[i-1][j] (skip) + dp[i-1][j-1] (take). Else dp[i][j] = dp[i-1][j]. O(m·n) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[i][0] = 1 for all i   // empty target
                      
                        2
                        for i in 1..m:
                      
                        3
                          for j in 1..n:
                      
                        4
                            dp[i][j] = dp[i-1][j]
                      
                        5
                            if s[i-1] == t[j-1]:
                      
                        6
                              dp[i][j] += dp[i-1][j-1]
                      
                        7
                        return dp[m][n]

Use when you need to count how many ways one string can form another.

Mental Trigger

“Count ways to form target from source” → Distinct Subsequences.

Java Template

public int numDistinct(String s, String t) {
    int m = s.length();
    int n = t.length();

    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++)
        dp[i][0] = 1;

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

            dp[i][j] = dp[i - 1][j];

            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

def num_distinct(s, t):
    m = len(s)
    n = len(t)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):

            dp[i][j] = dp[i - 1][j]

            if s[i - 1] == t[j - 1]:
                dp[i][j] += dp[i - 1][j - 1]

    return dp[m][n]

int numDistinct(string& s, string& t) {
    int m = s.size();
    int n = t.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; i++)
        dp[i][0] = 1;

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

            dp[i][j] = dp[i - 1][j];

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

    return dp[m][n];
}

function numDistinct(s, t) {
  const m = s.length;
  const n = t.length;

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

  for (let i = 0; i <= m; i++)
    dp[i][0] = 1;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j];

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

  return dp[m][n];
}

What Does `dp[i][j]` Mean?

Number of ways to form first j characters of t
using first i characters of s

Two Choices

Skip source character
→ dp[i - 1][j]

Use source character if it matches
→ dp[i - 1][j - 1]

Count subsequences = Skip + Match.

8. Palindrome DP

Use when the problem asks about palindromes inside a string.

Common Problems

Longest Palindromic Subsequence
Longest Palindromic Substring
Palindrome Partitioning

Mental Trigger

“Palindrome + range [i…j]” → Palindrome DP.

Base Template: Palindromic Substring

Longest Palindromic Substring

Longest substring that reads the same forwards and backwards.

dp[i][j] = true if s[i..j] is a palindrome. Base: single chars true. Extend: if s[i]==s[j] and dp[i+1][j-1] is true (or length ≤ 2), then dp[i][j] = true. Track the longest i..j.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for i in 0..n-1: dp[i][i] = true
                      
                        2
                        for len in 2..n:
                      
                        3
                          for i in 0..n-len:
                      
                        4
                            j = i + len - 1
                      
                        5
                            if s[i]==s[j] and (len<=2 or dp[i+1][j-1]):
                      
                        6
                              dp[i][j] = true; best = len
                      
                        7
                        return best

public int longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];

    int best = 0;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {

            if (s.charAt(i) == s.charAt(j) &&
                (j - i <= 2 || dp[i + 1][j - 1])) {

                dp[i][j] = true;
                best = Math.max(best, j - i + 1);
            }
        }
    }

    return best;
}

def longest_palindrome(s):
    n = len(s)

    dp = [[False] * n for _ in range(n)]

    best = 0

    for i in range(n - 1, -1, -1):
        for j in range(i, n):

            if s[i] == s[j] and (
                j - i <= 2 or dp[i + 1][j - 1]
            ):
                dp[i][j] = True
                best = max(best, j - i + 1)

    return best

int longestPalindrome(string& s) {
    int n = s.size();

    vector<vector<bool>> dp(n, vector<bool>(n, false));

    int best = 0;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {

            if (s[i] == s[j] &&
                (j - i <= 2 || dp[i + 1][j - 1])) {

                dp[i][j] = true;
                best = max(best, j - i + 1);
            }
        }
    }

    return best;
}

function longestPalindrome(s) {
  const n = s.length;

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

  let best = 0;

  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (
        s[i] === s[j] &&
        (j - i <= 2 || dp[i + 1][j - 1])
      ) {
        dp[i][j] = true;
        best = Math.max(best, j - i + 1);
      }
    }
  }

  return best;
}

What Does `dp[i][j]` Mean?

dp[i][j] = is substring s[i...j] a palindrome?

Transition

First character == last character
AND
inside is palindrome

Palindrome DP = Compare both ends + solve inside range.

9. Interval DP

Use when the problem is solved over a range [i...j].

Common Problems

Burst Balloons
Matrix Chain Multiplication
Merge Stones

Mental Trigger

“Solve something inside [i…j]” → Interval DP.

Base Template

Interval DP

Optimal answer over every range [i..j] by trying all splits.

Solve shorter ranges first, then combine: dp[i][j] = max over k in [i, j-1] of dp[i][k] + dp[k+1][j]. Lengths grow from 1 outward. O(n³) time, O(n²) space.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for len in 2..n:
                      
                        2
                          for i in 0..n-len:
                      
                        3
                            j = i + len - 1
                      
                        4
                            for k in i..j-1:
                      
                        5
                              dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])
                      
                        6
                        return dp[0][n-1]

public int intervalDP(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][n];

    for (int len = 2; len <= n; len++) {

        for (int i = 0; i + len - 1 < n; i++) {

            int j = i + len - 1;

            for (int k = i; k < j; k++) {

                int left = dp[i][k];
                int right = dp[k + 1][j];

                int cost = left + right;

                dp[i][j] = Math.max(
                    dp[i][j],
                    cost
                );
            }
        }
    }

    return dp[0][n - 1];
}

def interval_dp(nums):
    n = len(nums)

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):

        for i in range(n - length + 1):

            j = i + length - 1

            for k in range(i, j):
                left = dp[i][k]
                right = dp[k + 1][j]

                cost = left + right

                dp[i][j] = max(dp[i][j], cost)

    return dp[0][n - 1]

int intervalDP(vector<int>& nums) {
    int n = nums.size();

    vector<vector<int>> dp(n, vector<int>(n));

    for (int len = 2; len <= n; len++) {

        for (int i = 0; i + len - 1 < n; i++) {

            int j = i + len - 1;

            for (int k = i; k < j; k++) {

                int left = dp[i][k];
                int right = dp[k + 1][j];

                int cost = left + right;

                dp[i][j] = max(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

function intervalDP(nums) {
  const n = nums.length;

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

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      for (let k = i; k < j; k++) {
        const left = dp[i][k];
        const right = dp[k + 1][j];

        const cost = left + right;

        dp[i][j] = Math.max(dp[i][j], cost);
      }
    }
  }

  return dp[0][n - 1];
}

What Does `dp[i][j]` Mean?

Answer for range i...j

Main Idea

Try every split:

[i ........ j]

      k
      ↓

[i ... k] + [k+1 ... j]

Interval DP = Solve smaller ranges → Try every split → Build bigger range.

10. Partition DP

Use when the problem asks:

Where should I split the array/string?

Common Problems

Palindrome Partitioning II
Partition Array for Maximum Sum
Matrix Chain Multiplication

Mental Trigger

“Split into multiple parts” → Partition DP.

Base Template

Palindrome Partitioning II

Minimum cuts to split a string into palindrome pieces.

dp[i] = min cuts for prefix of length i. If s[j..i-1] is a palindrome, dp[i] = min(dp[i], dp[j] + 1). Precompute the palindrome table, then fill the 1-D dp left to right. O(n²) time.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dp[0] = -1   // trick: prefix length 0 needs -1 cuts
                      
                        2
                        for i in 1..n:
                      
                        3
                          dp[i] = i - 1
                      
                        4
                          for j in 0..i-1:
                      
                        5
                            if s[j..i-1] is palindrome:
                      
                        6
                              dp[i] = min(dp[i], dp[j] + 1)
                      
                        7
                        return dp[n]

public int partitionDP(int[] nums, int k) {
    int n = nums.length;

    int[] dp = new int[n + 1];

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < i; j++) {

            int cost = calculateCost(nums, j, i - 1);

            dp[i] = Math.max(
                dp[i],
                dp[j] + cost
            );
        }
    }

    return dp[n];
}

def partition_dp(nums, k):
    n = len(nums)

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i):
            cost = calculate_cost(nums, j, i - 1)

            dp[i] = max(dp[i], dp[j] + cost)

    return dp[n]

int partitionDP(vector<int>& nums, int k) {
    int n = nums.size();

    vector<int> dp(n + 1);

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < i; j++) {

            int cost = calculateCost(nums, j, i - 1);

            dp[i] = max(dp[i], dp[j] + cost);
        }
    }

    return dp[n];
}

function partitionDP(nums, k) {
  const n = nums.length;

  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      const cost = calculateCost(nums, j, i - 1);

      dp[i] = Math.max(dp[i], dp[j] + cost);
    }
  }

  return dp[n];
}

What Does `dp[i]` Mean?

Best answer for first i elements.

Main Idea

Try every previous cut:

0 ... j | j+1 ... i
        ↑
       cut

What Changed from Interval DP?

Interval DP:

dp[i][j]

works directly on a range.

Partition DP:

dp[i]

usually means the best answer for the first i elements, and we try every previous cut j.

Partition DP = Choose the best place to cut.

2DP Pattern Evolution

Grid DP
    ↓
dp[row][col]

Knapsack
    ↓
dp[item][capacity]
    ↓
Take / Skip

LCS
    ↓
dp[i][j]
    ↓
Compare two sequences

Edit Distance
    ↓
dp[i][j]
    ↓
Insert / Delete / Replace

Palindrome
    ↓
dp[i][j]
    ↓
Solve range

Interval DP
    ↓
dp[i][j]
    ↓
Try every split k

Partition DP
    ↓
dp[i]
    ↓
Try every cut j

Common Mistakes

Not defining `dp[i][j]`

Before coding, always ask:

What exactly does dp[i][j] represent?

Confusing subsequence and substring

Subsequence → can skip

Substring → must be continuous

Wrong knapsack transition

0/1:

dp[i - 1][cap - weight]

Unbounded:

dp[i][cap - weight]

Wrong loop direction in 1D knapsack

For 0/1:

for (int cap = capacity; cap >= weight; cap--)

For unbounded:

for (int cap = weight; cap <= capacity; cap++)

Forgetting base cases

Examples:

dp[i][0] = 0;
dp[0][j] = 0;

or:

dp[i][0] = 1;

depending on what the state represents.

Recognition Cheat Sheet

If you see…	Think…
Grid + paths	Grid DP
Capacity + each item once	0/1 Knapsack
Unlimited item reuse	Unbounded Knapsack
Two sequences + common	LCS
Two sequences + continuous	Longest Common Substring
Convert one string to another	Edit Distance
Count ways to form target	Distinct Subsequences
Palindrome + range	Palindrome DP
Solve `[i...j]`	Interval DP
Try every split/cut	Partition DP

Earn Premium with Referrals

Pattern Table

Mental Trigger

1. Grid DP

Common Problems

Mental Trigger

Base Template: Count Paths

Unique Paths

What Does dp[i][j] Mean?

Transition

Pattern 1.1: Minimum Path Sum

Java Code

What Changed from Base?

2. 0/1 Knapsack

0/1 Knapsack

Common Problems

Mental Trigger

Base Template

What Does dp[i][cap] Mean?

Two Choices

3. Unbounded Knapsack

Common Problems

Mental Trigger

Base Template

Unbounded Knapsack

What Changed from 0/1 Knapsack?

4. Longest Common Subsequence (LCS)

Longest Common Subsequence

Common Problems

Mental Trigger

Base Template

What Does dp[i][j] Mean?

Transition

5. Longest Common Substring

Mental Trigger

Longest Common Substring

Java Template

What Changed from LCS?

6. Edit Distance

Edit Distance

Mental Trigger

Java Template

What Does dp[i][j] Mean?

7. Distinct Subsequences

Distinct Subsequences

Mental Trigger

Java Template

What Does dp[i][j] Mean?

Two Choices

8. Palindrome DP

Common Problems

Mental Trigger

Base Template: Palindromic Substring

Longest Palindromic Substring

What Does dp[i][j] Mean?

Transition

9. Interval DP

Common Problems

Mental Trigger

Base Template

Interval DP

What Does dp[i][j] Mean?

Main Idea

10. Partition DP

Common Problems

Mental Trigger

Base Template

Palindrome Partitioning II

What Does dp[i] Mean?

Main Idea

What Changed from Interval DP?

2DP Pattern Evolution

Common Mistakes

Not defining dp[i][j]

Confusing subsequence and substring

Wrong knapsack transition

Wrong loop direction in 1D knapsack

Forgetting base cases

Recognition Cheat Sheet

Premium Content

What Does `dp[i][j]` Mean?

What Does `dp[i][cap]` Mean?

What Does `dp[i][j]` Mean?

What Does `dp[i][j]` Mean?

What Does `dp[i][j]` Mean?

What Does `dp[i][j]` Mean?

What Does `dp[i][j]` Mean?

What Does `dp[i]` Mean?

Not defining `dp[i][j]`