Dynamic programming solves problems with overlapping subproblems by remembering answers. Learn memoization and tabulation, greedy algorithms, and the recurring interview patterns that map a new problem to a known technique.
Dynamic programming applies when a problem breaks into overlapping subproblems — the same smaller computations recur. Naive recursion recomputes them, exploding to exponential time; DP stores each answer once and reuses it. Fibonacci is the canonical demo: the naive recursion is O(2ⁿ), but caching results makes it O(n). Spotting overlapping subproblems is the trigger for DP.
# naive recursion recomputes the same values exponentially — O(2^n)
def fib_slow(n):
if n < 2: return n
return fib_slow(n-1) + fib_slow(n-2) # fib(5) recomputes fib(2) 3 times
# MEMOIZATION (top-down DP): cache each answer once -> O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
# same recursion, but each fib(k) is computed ONCE. O(2^n) -> O(n).
# DP applies when subproblems OVERLAP (recur). If they don't, it's just D&C.DP comes in two styles. Top-down memoization keeps the natural recursion and caches results — easy to write from a recurrence. Bottom-up tabulation fills a table iteratively from the base cases up, avoiding recursion overhead and often reducing space. They compute the same thing; you choose based on clarity and whether you can shrink the table to O(1) space.
# bottom-up TABULATION: build answers from the base cases up, no recursion
def fib_table(n):
if n < 2: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # each cell from earlier cells
return dp[n]
# often you only need the last few cells -> O(1) space:
def fib_optimized(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# memoization (top-down) vs tabulation (bottom-up): same result, pick by clarity.Beyond Fibonacci, DP shines on optimization: "fewest coins to make an amount." The recurrence is that the best for amount n is one more than the best among n minus each coin. Filling a table bottom-up gives an O(amount × coins) solution to a problem whose brute force is exponential. Most DP problems reduce to finding this kind of recurrence.
# fewest coins to make 'amount' (or -1 if impossible)
def coin_change(coins, amount):
dp = [0] + [float("inf")] * amount # dp[a] = fewest coins to make a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1) # use coin c, +1
return dp[amount] if dp[amount] != float("inf") else -1
coin_change([1, 5, 6, 9], 11) # 2 (5 + 6)
# O(amount * len(coins)). The hard part is finding the recurrence:
# best(a) = 1 + min(best(a - c) for each coin c). The code follows from it.A greedy algorithm makes the locally best choice at each step and never reconsiders. When the problem has the right structure, this is optimal and far simpler than DP — interval scheduling (always take the earliest-finishing meeting) maximizes the count. The catch is that greedy is not always correct (coin change with arbitrary denominations can fail), so you must justify why the greedy choice is safe.
# max non-overlapping intervals: greedily pick the earliest-FINISHING one
def max_meetings(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count, end = 0, float("-inf")
for start, finish in intervals:
if start >= end: # doesn't overlap the last pick
count += 1
end = finish # commit — never reconsider
return count
max_meetings([(1,3), (2,4), (3,5), (0,6)]) # 2
# greedy is simpler than DP WHEN the local choice is provably safe.
# it is NOT always correct — e.g. coin change with odd denominations. Justify it.Most interview and real problems are variations on a small set of patterns. The winning skill is recognizing which one a new problem fits, so you reach for the right tool instead of inventing from scratch. Practice on a platform (LeetCode is the standard) builds this pattern-matching instinct — the true goal of studying DSA.
Recognize the pattern -> reuse the technique:
sorted array / pair-from-ends -> two pointers
contiguous subarray/substring "best" -> sliding window
"kth largest" / "top k" / median -> heap (top-k / two heaps)
numbers 1..n, find missing/duplicate -> cyclic sort / index-as-hash
linked-list cycle or middle -> fast & slow pointers
overlapping ranges -> sort + merge intervals
all combinations / permutations -> backtracking
"min/max ways" + overlapping subproblems -> dynamic programming
shortest path in a grid/graph -> BFS (unweighted) / Dijkstra
monotonic condition, find a threshold -> binary search on the answer
The skill isn't memorizing solutions — it's MATCHING a new problem to a
known pattern. That's what practice (LeetCode, etc.) trains.