Two signals that a problem is dynamic programming
Dynamic programming is really just smart recursion plus a notebook. Picture computing Fibonacci by plain recursion: fib(5) calls fib(4) and fib(3), fib(4) calls fib(3) again, and that same fib(3) gets recomputed a huge number of times. That repetition is the first signal, overlapping subproblems. If you write down each answer the first time you compute it, every later call becomes a free lookup and the exponential blowup disappears.
Two conditions must hold for DP to apply. First, overlapping subproblems: the recursion revisits the same inputs many times. (Contrast merge sort, whose subproblems are all distinct halves; that is divide and conquer, not DP.) Second, optimal substructure: an optimal solution to the whole is composed of optimal solutions to its parts, so you can combine sub-answers without reconsidering how each was formed. When both hold, caching each subproblem's result turns exponential work into polynomial.
Memoization vs tabulation
The same recurrence can be implemented two ways. Memoization (top-down) keeps your natural recursion but stores each result in a cache, a hash map or array keyed by the subproblem's arguments; before computing anything, you check the cache. It only ever computes the subproblems you actually reach, and it is easy to derive directly from a brute-force recursion.
Tabulation (bottom-up) drops recursion entirely and fills a table in dependency order, starting from the base cases and building up to the final answer. It avoids call-stack overhead and recursion-depth limits, and it makes space optimization obvious: often you only need the last row or two, so an O(n·W) table collapses to O(W). Reach for memoization when the recurrence is easy to see and the state space is sparse; reach for tabulation when you want tight control over fill order and memory.
Fibonacci, knapsack, and LCS
These three are the on-ramp. Fibonacci is the smallest example: the state is a single number n, the recurrence is f(n) = f(n-1) + f(n-2), and memoizing drops it from O(2^n) to O(n). It shows the mechanism with nothing else to distract you.
0/1 knapsack and longest common subsequence (LCS) add a second dimension to the state. Knapsack's state is (item index, remaining capacity), and each cell picks the better of "skip this item" or "take it"; it is the canonical example of why greedy fails and DP succeeds. LCS's state is (position in string A, position in string B), and each cell either extends a match or takes the best of dropping one character, the same table-filling shape that underlies edit distance and diff tools.
Once you have watched these three fill their tables cell by cell, most other DP problems become variations on the same move: define the state, write the recurrence, pin the base cases, decide the fill order. This is exactly the kind of thing that clicks faster when you see the table populate step by step instead of staring at the recurrence on paper.
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = best value using the first i items within weight limit w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
wt, val = weights[i - 1], values[i - 1]
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # skip item i
if wt <= w: # or take item i
dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)
return dp[n][capacity]DP replaces exponential naive recursion (O(2^n) for Fibonacci, for instance) with polynomial time. There is no best/worst/average split in the usual sense: the full state space is traversed, so the bound is tight.
When to use it
- A naive recursion recomputes the same inputs over and over (Fibonacci, recursive knapsack) and you want to collapse the exponential blowup with a cache.
- The problem asks for a count of ways, a min/max cost, or whether a target is reachable, over a bounded set of states (coin change, longest increasing subsequence, edit distance).
- Choices are constrained and you need the true global optimum, not a locally greedy pick, as in 0/1 knapsack where greedy provably fails.
- You are working over sequences or grids where each step's optimal answer depends on optimal answers to earlier, smaller subproblems.
Watch out for
- Reaching for DP when there is no overlap or no optimal substructure: if subproblems never repeat, memoization only adds overhead, and if substructure does not hold, the DP answer is simply wrong.
- Under-specifying the state, leaving out a dimension the recurrence actually depends on (like remaining capacity in knapsack), which silently returns subtly wrong results.
- Confusing greedy with DP: applying a greedy choice to 0/1 knapsack or coin change with arbitrary denominations gives incorrect answers, and off-by-one errors in base-case rows or columns break the table when converting recursion to tabulation.
Dynamic programming is one of the most feared tags in placement and FAANG-style interviews, and interviewers know it, so they care less about whether you instantly recall a trick and more about whether you can reason your way to it. A strong answer usually starts from a brute-force recursion, points out the repeated subproblems out loud, adds memoization, and then, if asked, converts to bottom-up tabulation and optimizes space. What they are actually grading: can you define the state clearly, write a correct recurrence with correct base cases, state time and space complexity honestly, and handle edge cases. Classic prompts include coin change, longest increasing subsequence, edit distance, house robber, and knapsack variants.