Dynamic Programming

Solve a problem once by breaking it into overlapping subproblems and reusing their answers, instead of recomputing them exponentially.

Key ideas

  • —DP needs optimal substructure plus overlapping subproblems.
  • —Define the state precisely — what does dp[i] mean? — before writing any transition.
  • —Top-down memoization and bottom-up tabulation are two encodings of the same recurrence.

State and transition

Every DP starts with a clear definition of state: a value like dp[i] that captures the answer to a subproblem. The transition expresses dp[i] in terms of smaller states. If you cannot write a sentence describing exactly what dp[i] holds, the recurrence will be wrong. Climbing Stairs and House Robber are the canonical one-dimensional warm-ups.

Memoization vs tabulation

Top-down memoization writes the recursion directly and caches results the first time each state is computed. Bottom-up tabulation fills a table in dependency order, often letting you shrink memory to a rolling window of the last few rows. They compute the same values; choose whichever makes the dependencies clearer for the problem at hand.

Two-dimensional DP

Many string and grid problems use a two-index state: dp[i][j] over prefixes of two strings (Edit Distance, Longest Common Subsequence) or positions in a grid (Unique Paths). The transition compares characters or sums adjacent cells. Drawing the table by hand for a tiny input is the fastest way to confirm your recurrence before coding it.

Practice this

Sources

← All lessonsNext: Backtracking →