Dynamic programming sounds intimidating but the core idea is simple: if you solve the same subproblem more than once, cache the answer and reuse it. That one principle transforms the naive exponential Fibonacci into a linear computation, and the brute-force 0-1 knapsack into a polynomial algorithm. The challenge is recognising when DP applies and designing the state correctly.
What changed in 2026
- LLMs explain DP but still struggle to design state. AI assistants can reproduce textbook DP solutions but often produce incorrect recurrences on novel problems. Understanding state design is still a human skill.
- DP is common in competitive AI inference. KV-cache in transformer inference is a form of memoisation — caching attention computations across tokens. The concept is everywhere.
- Interview expectations shifted. Exhaustive DP drilling declined at some companies, but recognising DP applicability and articulating the recurrence clearly remains a strong signal.
functools.cache is now preferred over lru_cache(maxsize=None) in Python 3.9+. It is faster, has better type inference, and communicates intent clearly.
Two necessary conditions for DP
1. Optimal substructure: The optimal solution to the problem is composed of optimal solutions to its subproblems.
- Shortest path: optimal path from A to C via B = optimal A→B + optimal B→C. ✓
- Longest path (no weights): not optimal substructure; DP does not apply. ✗
2. Overlapping subproblems: The same subproblems appear repeatedly in the recursion tree.
- Fibonacci:
fib(5) calls fib(4) and fib(3); fib(4) also calls fib(3). ✓
- Binary search: each subproblem is independent (different half of array). ✗ — use divide and conquer, not DP.
Top-down vs bottom-up
| Aspect |
Top-down (memoisation) |
Bottom-up (tabulation) |
| Code style |
Recursive + cache |
Iterative + table |
| Ease of writing |
Easier — start from the recursive solution |
Harder — must determine fill order |
| Overhead |
Call-stack frames, dict/map lookups |
None — direct array access |
| Stack overflow risk |
Yes for deep recursion |
No |
| Space optimisation |
Harder |
Easy — can often use rolling arrays |
Top-down example: Fibonacci
from functools import cache
@cache
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
Bottom-up example: Fibonacci
def fib(n: int) -> int:
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
The bottom-up version uses O(1) space instead of O(n). Recognising when you only need the last k rows/values is one of the most common DP optimisations.
The six core DP patterns
| Pattern |
Canonical problem |
State dimensions |
| 1D linear |
Climbing stairs, house robber |
dp[i] |
| 2D grid |
Unique paths, minimum path sum |
dp[i][j] |
| Knapsack |
0-1 knapsack, coin change |
dp[i][w] |
| LCS/LIS |
Longest common subsequence |
dp[i][j] |
| Interval |
Matrix chain multiplication |
dp[i][j] |
| Tree DP |
Diameter of binary tree |
dp[node] |
Knapsack example (coin change)
def coin_change(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
State: dp[a] = minimum coins to make amount a. Recurrence: dp[a] = min(dp[a - c] + 1) for each coin c ≤ a.
State design process
- Define what the state represents.
dp[i] = answer for the first i elements.
- Write the recurrence. How does
dp[i] depend on earlier states?
- Identify base cases. What are the trivially known values (empty input, zero amount)?
- Choose fill order. Bottom-up must fill states in an order where dependencies are already computed.
- Optimise space if needed. If
dp[i] only depends on dp[i-1], keep only two variables.
Time and space complexity
| Problem |
Time |
Space |
Optimised space |
| Fibonacci |
O(n) |
O(n) top-down |
O(1) bottom-up |
| Longest common subseq. |
O(nm) |
O(nm) |
O(min(n,m)) rolling |
| 0-1 knapsack |
O(nW) |
O(nW) |
O(W) 1D array |
| Edit distance |
O(nm) |
O(nm) |
O(min(n,m)) |
How to pick
- Does the problem ask for an optimum (min/max) or count? → Strong DP signal.
- Can you define a recursive solution with overlapping subproblems? → Add memoisation.
- Is n ≤ ~10 000 and W ≤ ~10 000? → O(nW) DP fits in memory and time.
- Are subproblems independent? → Divide and conquer (merge sort, quick sort) — not DP.
- Does the recursion blow the stack? → Convert to bottom-up tabulation.
Common mistakes
Incorrect recurrence direction. For a knapsack variant, iterating the capacity forward vs backward can flip the problem from unbounded to 0-1 knapsack. Know which variant you need.
Off-by-one in state indexing. Defining dp[i] as "the first i elements" vs "ending at index i" produces different recurrences and different base cases. Commit to one definition clearly.
Forgetting the base case. Missing dp[0] = 0 or dp[0][0] = 1 causes the whole table to propagate the wrong initial value.
Not clearing the cache between test cases. If using @cache in a competitive-programming context with multiple test cases, call fib.cache_clear() between runs.
What to skip
- DP for greedy-solvable problems. Interval scheduling, activity selection, and fractional knapsack have greedy O(n log n) solutions; DP is heavier than necessary.
- 2D DP when a 1D rolling array suffices. If
dp[i][j] only depends on dp[i-1][*], store only the current and previous rows.
- Memoising with mutable arguments.
@cache on a function that takes a list fails; convert to tuples. See Recursion explained in 2026 for related memoisation patterns.
FAQ
What is the difference between DP and greedy?
Both solve optimisation problems, but greedy makes a locally optimal choice at each step without reconsidering. DP explores all choices via subproblems. Greedy is faster but only correct for certain problem structures.
Is DP only for 1D and 2D problems?
No. DP state can have any number of dimensions. TSP (travelling salesman) uses a bitmask DP with O(n² 2^n) complexity. Practicality is the constraint, not structure.
How do I know if my recurrence is correct?
Start with a tiny example (n = 3), trace the table by hand, and verify it matches the brute-force answer. Then test on edge cases (empty input, single element, all same values).
Can LLMs solve DP problems reliably?
They reproduce known patterns (Fibonacci, knapsack, LCS) accurately. On novel problem descriptions or unusual constraints they often produce plausible but wrong recurrences. Always verify the logic.
Where to go next