Level 3 · 50 min

DP: Memoization, Tabulation, State Compression

Dynamic programming is for problems with overlapping subproblems and optimal substructure. The practical skill is defining state so each subproblem has one clear meaning.

State comes before recurrence

A DP state must answer a precise question: best value using first i items and capacity c, number of ways to reach sum s after i steps, or edit distance between prefixes i and j. If the state is vague, the recurrence will be wrong.

Memoization vs tabulation

Memoization writes the natural recursive solution and caches states on demand. Tabulation fills states in dependency order, often with lower overhead and easier memory control. Both compute the same state graph when implemented correctly.

Compress only after correctness

Many DP tables only need the previous row or a narrow band of states. Compressing memory from O(nm) to O(m) is useful, but update order becomes part of correctness. If current row reads previous row, iterate in the direction that prevents overwriting needed values.

Key Takeaways

A DP state is a contract: define exactly what the value means.
Memoization and tabulation differ in traversal order, not in the mathematical subproblems.
Memory compression changes dependency hazards; prove update order before optimizing.

Code example

function fibonacci(n):
  dp = array(n + 1, fill = 0)
  dp[0] = 0
  dp[1] = 1
  for i from 2 to n:
    dp[i] = dp[i - 1] + dp[i - 2]
  return dp[n]