Skip to content

Dynamic Programming

Dynamic programming solves problems with overlapping subproblems and optimal substructure by evaluating each relevant state once.

Four design steps

  1. Define a state with an unambiguous meaning.
  2. Derive a recurrence from smaller states.
  3. Establish base cases and a valid evaluation order.
  4. Recover a solution if values alone are insufficient.

Longest common subsequence length

Let dp[i][j] be the LCS length of prefixes left[0..i) and right[0..j).

dp[0][j] = dp[i][0] = 0
if left[i - 1] == right[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1]
otherwise: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

The table has (m + 1)(n + 1) states and Θ(1) work per state, giving Θ(mn) time and Θ(mn) space. If only the length is needed, two rows reduce space to Θ(min(m, n)).

Memoization versus tabulation

  • top-down memoization evaluates reachable states on demand and uses recursion;
  • bottom-up tabulation makes dependency order and memory reduction explicit.

Common mistakes

  • a state that omits information needed for future decisions;
  • a recurrence that permits invalid combinations;
  • overwriting values before all dependents consume them;
  • claiming polynomial time without counting the state dimensions.

Exercises

  1. Design states for edit distance.
  2. Explain why naive Fibonacci recursion repeats work.
  3. Recover an actual LCS from the full table.