DP Basics
What Is Dynamic Programming?
Dynamic Programming (DP) is an algorithmic technique that solves problems by breaking them into overlapping sub-problems, solving each sub-problem once, and storing the result to avoid redundant recomputation.
THE CORE IDEA:
"Those who cannot remember the past are condemned to recompute it."
Naive recursion: Solve each sub-problem fresh every time
→ exponential time from repeated work
Dynamic Programming: Solve each unique sub-problem exactly once
→ store result, reuse when needed
→ polynomial time
NOT THE SAME AS:
Divide & Conquer: Sub-problems are INDEPENDENT (merge sort, quick sort)
→ no benefit from storing results
→ each sub-problem is unique and non-overlapping
Greedy: Make locally optimal choice at each step
→ never look back, never revisit
→ only correct for specific problem structures
DP: Sub-problems OVERLAP (same sub-problem appears many times)
→ storing results pays off enormously
→ globally optimal via considering all choices
The Two Required Properties
A problem must have BOTH properties for DP to apply.
Property 1: Overlapping Subproblems
The same sub-problem is solved multiple times in a naive recursive approach.
Fibonacci naive recursion tree for fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ... ... ...
fib(3) computed TWICE
fib(2) computed THREE TIMES
fib(1) computed FIVE TIMES
For fib(50): fib(2) is recomputed 2,971,215,073 times!
WITH DP: compute each unique sub-problem once and store it.
fib(0), fib(1), fib(2), ..., fib(50) — each computed exactly once.
Total computations: 51 instead of ~2^50.
Property 2: Optimal Substructure
The optimal solution to the whole problem can be constructed from optimal solutions to its sub-problems.
SHORTEST PATH:
Shortest path from A to C via B =
shortest path A→B + shortest path B→C
The sub-paths must themselves be shortest paths.
→ Has optimal substructure ✓
LONGEST PATH (in graph with cycles):
Longest path from A to C via B ≠
longest path A→B + longest path B→C
Because the sub-paths might share vertices.
→ No optimal substructure ✗ (DP doesn't directly apply)
FIBONACCI:
fib(n) = fib(n-1) + fib(n-2)
The sub-problem answers combine directly.
→ Has optimal substructure ✓
MATRIX CHAIN MULTIPLICATION:
Optimal parenthesisation of A1...An can be split at some k:
(A1...Ak) × (Ak+1...An)
Each half must itself be optimally parenthesised.
→ Has optimal substructure ✓
The Classic Example: Fibonacci
Fibonacci perfectly illustrates the progression from naive recursion → DP.
Naive Recursion — O(2ⁿ)
fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) Problem: fib(5) spawns 15 calls. fib(40) spawns ~1 billion calls. Same sub-problems recomputed exponentially many times.
Memoized (Top-Down DP) — O(n)
memo = {}
fib(n):
if n in memo: return memo[n] ← look up before computing
if n <= 1: return n
memo[n] = fib(n-1) + fib(n-2) ← store before returning
return memo[n]
Each unique sub-problem computed ONCE.
15 calls → 9 unique calls for fib(5).
fib(40) → 41 calls.
Tabulated (Bottom-Up DP) — O(n) time, O(n) space
dp[0] = 0, dp[1] = 1 for i from 2 to n: dp[i] = dp[i-1] + dp[i-2] No recursion. Fill table left to right. Each value used exactly when needed.
Space-Optimised — O(n) time, O(1) space
prev2 = 0, prev1 = 1 for i from 2 to n: curr = prev1 + prev2 prev2 = prev1 prev1 = curr return prev1 Only two variables needed at any time.
1public class FibonacciDP {
2
3 // ── 1. Naive recursion — O(2^n) time ──────────────────────────────
4 public static long fibNaive(int n) {
5 if (n <= 1) return n;
6 return fibNaive(n - 1) + fibNaive(n - 2);
7 }
8
9 // ── 2. Memoized top-down DP — O(n) time, O(n) space ───────────────
10 public static long fibMemo(int n, long[] memo) {
11 if (n <= 1) return n;
12 if (memo[n] != -1) return memo[n]; // Cache hit — return stored
13 memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
14 return memo[n];
15 }
16
17 // ── 3. Tabulated bottom-up DP — O(n) time, O(n) space ─────────────
18 public static long fibTab(int n) {
19 if (n <= 1) return n;
20 long[] dp = new long[n + 1];
21 dp[0] = 0; dp[1] = 1;
22 for (int i = 2; i <= n; i++) {
23 dp[i] = dp[i - 1] + dp[i - 2]; // Fill table left to right
24 }
25 return dp[n];
26 }
27
28 // ── 4. Space-optimised — O(n) time, O(1) space ────────────────────
29 public static long fibOpt(int n) {
30 if (n <= 1) return n;
31 long prev2 = 0, prev1 = 1;
32 for (int i = 2; i <= n; i++) {
33 long curr = prev1 + prev2;
34 prev2 = prev1;
35 prev1 = curr;
36 }
37 return prev1;
38 }
39
40 public static void main(String[] args) {
41 int n = 10;
42
43 // Naive — safe only for small n
44 System.out.println("Naive fib(10): " + fibNaive(n));
45
46 // Memoized — initialise memo with -1 (sentinel for "not computed")
47 long[] memo = new long[n + 1];
48 java.util.Arrays.fill(memo, -1);
49 System.out.println("Memoized fib(10): " + fibMemo(n, memo));
50
51 // Tabulated
52 System.out.println("Tabulated fib(10): " + fibTab(n));
53
54 // Space-optimised
55 System.out.println("Optimised fib(10): " + fibOpt(n));
56
57 // Large n — only DP versions can handle this
58 System.out.println("Optimised fib(50): " + fibOpt(50));
59 }
60}Output:
Naive fib(10): 55
Memoized fib(10): 55
Tabulated fib(10): 55
Optimised fib(10): 55
Optimised fib(50): 12586269025
Visualising the Sub-problem DAG
Fibonacci sub-problem graph for fib(6):
Without DP (tree — same node recomputed multiple times):
fib(6)
/ \
fib(5) fib(4)
/ \ / \
fib(4) fib(3) fib(3) fib(2)
... ... ... ...
(exponential branches, massive repeated work)
With DP (DAG — each unique sub-problem appears exactly once):
fib(0) ─→ fib(2) ─→ fib(3) ─→ fib(4) ─→ fib(5) ─→ fib(6)
fib(1) ─→ ─→ ─→ ─→
(each node computed once; arrows = "depends on")
KEY INSIGHT:
The tree representation shows exponential CALLS.
The DAG representation shows the actual unique WORK.
DP processes the DAG — O(n) nodes, O(n) work total.
DP vs Greedy vs Divide & Conquer
SUB-PROBLEMS CHOICE STRATEGY COMPLEXITY
──────────── ───────────────── ───────────
Divide & Conquer Non-overlapping Divide then merge O(n log n)
(unique) (always split) typically
Greedy Overlapping Locally best now O(n) or
(but greedy never reconsider O(n log n)
choice correct)
Dynamic Overlapping Try all choices, Polynomial
Programming (same sub-prob remember results, O(n²), O(n³)
solved many pick globally best typically
times in naive)
WHEN GREEDY WORKS (subset of DP problems):
Greedy is provably optimal when the problem has the
"greedy choice property": local optimum → global optimum.
Examples: MST (Kruskal/Prim), Dijkstra's, Activity Selection.
For Coin Change (arbitrary denominations):
Greedy FAILS: denominations [1, 3, 4], target = 6
Greedy picks 4+1+1 = 3 coins.
DP finds 3+3 = 2 coins. ✓
EXAMPLES BY TECHNIQUE:
Divide & Conquer: Merge Sort, Quick Sort, Binary Search, FFT
Greedy: Dijkstra, Kruskal, Prim, Huffman Coding
DP: Knapsack, LCS, LIS, Edit Distance, Matrix Chain
Recognising DP Problems
STRONG SIGNALS that a problem needs DP: 1. COUNTING: "how many ways to..." → Ways to climb stairs, ways to make change, unique paths in grid 2. OPTIMISATION: "minimum/maximum/shortest/longest..." → Coin change minimum coins, longest common subsequence 3. EXISTENCE: "is it possible to..." → Can you reach target sum, can a string be segmented 4. DECISION with CHOICES at each step: → At each stair you can take 1 or 2 steps; choose which 5. OVERLAPPING structure visible in naive recursion: → Draw the recursion tree; if same node appears twice → DP COMMON DP PROBLEM SHAPES: Sequence → 1D DP (Fibonacci, Climbing Stairs, House Robber) Two strings → 2D DP (LCS, Edit Distance, LCS) Grid → 2D DP (Unique Paths, Min Path Sum) Subsets → 1D/2D DP (0/1 Knapsack, Subset Sum) Intervals → 2D DP (Matrix Chain, Burst Balloons) NOT DP: Finding ONE specific element (use binary search or sorting) Graph connectivity (use BFS/DFS) Problems with no recurrence structure
The Four Steps to Solve Any DP Problem
STEP 1: DEFINE the sub-problem and state
"What does dp[i] (or dp[i][j]) represent?"
This is the hardest step. The state must:
- Fully describe what information is needed to solve the sub-problem
- Be small enough to fit in memory
- Lead to a valid recurrence
STEP 2: WRITE the recurrence (state transition)
"How does dp[i] depend on smaller sub-problems?"
Express dp[i] = f(dp[i-1], dp[i-2], ...)
This is the heart of the DP solution.
STEP 3: IDENTIFY base cases
"What are the smallest sub-problems with known answers?"
dp[0] = ?, dp[1] = ? — these anchor the recurrence.
STEP 4: DETERMINE computation order
Top-down (memoization): recursion handles order automatically
Bottom-up (tabulation): must fill table so dependencies are
computed before they are needed
EXAMPLE — Climbing Stairs:
You can take 1 or 2 steps. In how many ways can you reach step n?
Step 1: dp[i] = number of distinct ways to reach step i
Step 2: dp[i] = dp[i-1] + dp[i-2]
(you arrived from step i-1 via 1 step,
or from step i-2 via 2 steps)
Step 3: dp[0] = 1 (one way to stay at bottom — do nothing)
dp[1] = 1 (one way to reach step 1 — take one step)
Step 4: Fill dp[2], dp[3], ..., dp[n] left to right
dp[2] = dp[1]+dp[0] = 2
dp[3] = dp[2]+dp[1] = 3
dp[4] = dp[3]+dp[2] = 5
...same as Fibonacci shifted by one!
Time and Space Complexity Framework
TIME COMPLEXITY: Total work = (number of unique sub-problems) × (work per sub-problem) Fibonacci: n sub-problems × O(1) each = O(n) LCS: n×m sub-problems × O(1) each = O(n×m) Knapsack: n×W sub-problems × O(1) each = O(n×W) Matrix Chain: O(n²) sub-problems × O(n) each = O(n³) SPACE COMPLEXITY: Full table: O(number of sub-problems) Optimised: Often reducible by noting only recent rows/values needed Fibonacci: O(n) table → O(1) with two variables LCS n×m: O(n×m) → O(min(n,m)) with rolling row Knapsack n×W: O(n×W) → O(W) with 1D table ALWAYS ASK: Do I need the full table (to reconstruct the path/sequence)? → Keep full table If I only need the final value: → Can I reduce to a rolling array or just two variables?
Common Mistakes
Defining the sub-problem incorrectly. If dp[i] doesn't capture all information needed to answer the sub-problem, the recurrence will be wrong. Example: for "longest path in a grid with obstacles", dp[i][j] = length of longest path to (i,j) is correct. But dp[i] = "length of longest path ending at row i" is too coarse — it loses column information.
Forgetting base cases. The recurrence works for i ≥ some threshold; below that, values must be initialised explicitly. Missing dp[0] or dp[1] typically causes wrong answers silently or array out-of-bounds.
Wrong computation order in bottom-up. When computing dp[i][j], its dependencies (dp[i-1][j], dp[i][j-1], etc.) must already be filled. If you fill the table in the wrong order, you read stale values. Always trace: "when computing dp[i][j], what cells do I need?" and verify they're filled first.
Using the memoized version when iterative space optimisation is needed. Recursion has a call stack overhead. For large n (n > 10,000 in Python), recursive memoization hits the recursion limit. Switch to iterative bottom-up for large inputs.
Not initialising the memo correctly. The memo must distinguish "not yet computed" from "computed as 0 or -1". A common bug: use 0 as sentinel but 0 is also a valid answer. Use -1 (for non-negative answers), None (Python), or a separate boolean array.
Interview Questions
Q: What are the two properties required for DP, and how do you verify them?
Optimal substructure: verify that the optimal answer to the whole problem can be composed from optimal answers to sub-problems. Test by contradiction — if you use a sub-optimal sub-solution, does it always produce a sub-optimal total? If yes, optimal substructure holds. Overlapping sub-problems: draw the naive recursion tree for a small input. If the same node appears more than once, sub-problems overlap. If every node is unique, divide-and-conquer is more appropriate.
Q: How do you decide the DP state (what dp[i] should represent)?
Start from the answer you need. The DP state must encode all information needed to solve the sub-problem without referencing global state. For sequences, dp[i] often means "answer for the first i elements" or "answer ending at position i." For two sequences, dp[i][j]. For subset problems, dp[i][w] where w is a capacity. The state is too coarse if different inputs with the same state need different answers — add more dimensions.
Q: When should you use DP versus a greedy algorithm?
Use greedy when the problem has the greedy choice property — a locally optimal choice always leads to a globally optimal solution. This is true for activity selection, MST, and Dijkstra's. Use DP when the greedy choice isn't provably correct — you need to consider all options and pick the best. Coin change with arbitrary denominations is the classic case where greedy fails (picks fewer large coins) but DP gives the correct minimum. If unsure, try to construct a counter-example for greedy; if you can, use DP.
Summary
Dynamic Programming solves problems by breaking them into overlapping sub-problems, solving each exactly once, and storing results for reuse.
Two required properties:
- ›Optimal substructure — optimal answer is built from optimal sub-answers
- ›Overlapping sub-problems — naive recursion solves the same sub-problem many times
Two implementation styles:
- ›Memoization (top-down) — recursion + cache; lazy; natural to write; may hit recursion depth limits
- ›Tabulation (bottom-up) — iterative; fills table in dependency order; usually faster in practice
Four steps to solve any DP problem:
- ›Define the sub-problem — what does dp[i] represent?
- ›Write the recurrence — how does dp[i] depend on smaller values?
- ›Identify base cases — what are the smallest known answers?
- ›Determine computation order — fill dependencies before they're needed
Fibonacci progression shows the complete story: naive O(2ⁿ) → memoized O(n) → tabulated O(n) → space-optimised O(1) space.
In the next topic you will explore State Transition Thinking — how to systematically derive recurrences for any DP problem by defining states, transitions, and base cases.
Dynamic Programming requires two properties to be applicable. What are they?