Dynamic Programming

Subsequence DP

LIS, LCS and edit distance: state over one or two sequence prefixes.

Hard, about 100 minutes to practise.

1Understand

The idea

For two sequences, dp[i][j] is the answer for the prefixes a[:i] and b[:j]. If the last characters match, extend dp[i−1][j−1]; otherwise take the best of dropping one character from either side. Edit distance, LCS and their variations differ only in that transition.

Intuition

For two sequences, dp[i][j] is the answer for prefixes a[:i] and b[:j]. If the last characters match, extend dp[i-1][j-1]; otherwise take the best of dropping from either side.

Edit distance, LCS and related problems differ mainly in the cost of that transition. Fill by increasing i,j so smaller prefixes are ready.

This is not the same as substring DP (contiguous), subsequence allows skips.

What you will be able to do

  • Use prefix-length indices (i-1 for characters)
  • Know the O(n log n) LIS trick

When to use it

  • Longest increasing / common subsequence
  • Minimum edits to transform strings
  • Two strings compared prefix by prefix

2See it

Walkthrough

LIS length

nums = [10, 9, 2, 5], dp[i] = best ending at i.

1 / 5

i
10
9
2
5
0123
i → index 0

Each dp[i] starts at 1 (the element alone).

dp = [1]*n

Live template

Line 1 active

1dp = [[0] * (m + 1) for _ in range(n + 1)]
2for i in range(1, n + 1):
3 for j in range(1, m + 1):
4 dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])

Complexity: time O(n·m), space O(n·m) → O(m)

Time and space O(n·m); space can drop to O(min(n,m)) with two rows. Recursive without memo is exponential. For only length of LCS you do not need the string reconstruction table.

Read the walkthrough as text

Edit distance. word1 = "horse", word2 = "ros".

  1. dp[0][j] = j, dp[i][0] = i (insert/delete all).
  2. At h vs r: replace → from diagonal + 1.
  3. Continue; when s matches s (in horse vs ros), diagonal carries without cost.
  4. Final dp[5][3] = 3 (replace h→r, delete o/e appropriately, classic answer 3).

LCS uses +1 on match and max on mismatch instead of min of edit ops.

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Longest increasing subsequence

    Example. LIS length in O(n log n).

    How. Patience piles: binary search placement position for each x; or O(n²) table.

  • Longest common subsequence

    Example. LCS of two strings.

    How. dp[i][j] = +1 if match else max(dp[i-1][j], dp[i][j-1]) on prefixes.

  • Edit distance

    Example. Minimum insert/delete/replace to match strings.

    How. Same 2D table: match diagonal, else 1 + min of three neighbours.

  • Distinct subsequences

    Example. Count s subsequences equal to t.

    How. If s[i]==t[j]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else carry dp[i-1][j].

  • Interleaving strings

    Example. Is s3 an interleave of s1 and s2?

    How. dp[i][j] whether s1[:i] and s2[:j] can form s3[:i+j].

  • Pattern matching with wildcards (regex, wildcard)

    Example. Match pattern with * and ? wildcards.

    How. 2D boolean DP: ? matches one char; * matches empty or extend.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Index shift

    Why it happens. dp[i] lines up with s[i] mentally.

    How it fails. LCS uses a[i] when dp[i] meant prefix length i, off-by-one on first character.

    Fix. dp[i][j] is prefixes a[:i] and b[:j]; compare a[i-1] and b[j-1].

  • Substring vs subsequence

    Why it happens. Contiguous vs skipping chars is an easy miss in the problem statement.

    How it fails. Longest common substring DP allows gaps, reports subsequence length.

    Fix. Substring DP resets on mismatch; subsequence allows max of skip-left/skip-up.

  • Empty prefix row

    Why it happens. Main double loop can run from 0.

    How it fails. Edit distance without dp[0][j]=j base, first row undefined, costs wrong.

    Fix. Zero-th row/column encode empty-prefix costs before nested loops.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons