Algorithms
Dynamic Programming Memoization
Dynamic Programming (DP) transforms exponential recursive solutions into polynomial-time algorithms by storing and reusing the results of overlapping subproblems. It applies when a problem has optimal substructure (an optimal solution is built from optimal sub-solutions) and overlapping subproblems (the same subproblem recurs many times). DP is the single most important algorithm paradigm in coding interviews.
01
Section One · Foundation
What is Dynamic Programming?
Dynamic programming breaks a problem into smaller overlapping subproblems, solves each once, stores the result in a table (memoisation or DP array), and reuses stored results to avoid redundant computation. The classic naive recursive Fibonacci has O(2ⁿ) time because it recomputes f(k) for every path; DP reduces this to O(n) by computing each f(k) exactly once. Two implementation styles exist: top-down memoization (recursive with a cache) and bottom-up tabulation (iterative, filling a table from base cases up).
Analogy: Imagine computing the total cost of all routes through a city. Instead of recalculating the distance from node B to the destination every time you arrive at B by a different route, you write it down the first time. The next time you reach B, you look up the stored answer in O(1). This is exactly what the DP table does — a lookup table of pre-solved subproblem answers.
Prerequisites for DP Applicability
Optimal Substructure
▶
The optimal solution to the full problem can be constructed from optimal solutions to sub-problems (e.g. shortest path, minimum cost).
Overlapping Subproblems
▶
The same sub-problems recur — unlike divide-and-conquer (Merge Sort) which creates independent non-overlapping sub-problems.
Define the DP State
▶
dp[i] or dp[i][j] must fully describe the sub-problem. The state definition is the hardest and most important part of DP.Recurrence Relation
▶
Express
dp[i] as a function of smaller states (e.g. dp[i] = dp[i-1] + dp[i-2] for Fibonacci). Write this before coding.Top-Down Memoization
- Recursive + cache (HashMap or array)
- Only solves needed subproblems
- Easier to write from the recursive formulation
- Stack overflow risk on deep recursion
Bottom-Up Tabulation
- Iterative + DP table (array)
- Solves all subproblems in topological order
- Better cache performance, no recursion overhead
- Can often optimise space (rolling array)
02
Section Two · Core Patterns
DP Patterns & Problem Families
1D DP — Linear Sequence (Fibonacci, Climbing Stairs, House Robber)
State depends on a constant number of previous states. dp[i] = f(dp[i-1], dp[i-2], …). Space can usually be compressed to O(1).
| Step | Action (Fibonacci) | State After |
|---|---|---|
| 1 | Define dp[i] = i-th Fibonacci number; base cases dp[0]=0, dp[1]=1 | dp[0..1] initialized |
| 2 | Fill dp[i] = dp[i-1] + dp[i-2] for i from 2 to n | dp[0..n] fully filled |
| 3 | Return dp[n]; optimise to O(1) space using two variables prev, curr | Answer in O(n) time, O(1) space |
Pattern: Whenever you see "number of ways to reach step n" or "max profit with no two adjacent elements selected", it's 1D DP. Recognise the recurrence first, then implement.
2D DP — Grid / Two-Sequence (LCS, Edit Distance, Knapsack, LPS)
State depends on two variables (indices into two strings/sequences, or item+capacity). dp[i][j] = optimal answer for first i elements of A and first j elements of B.
| Step | Action (LCS — Longest Common Subsequence) | State After |
|---|---|---|
| 1 | dp[i][j] = LCS length of A[0..i-1] and B[0..j-1]; base: dp[0][j]=dp[i][0]=0 | First row/column zeroed |
| 2 | If A[i-1]==B[j-1]: dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) | Table filled row by row |
| 3 | Answer is dp[m][n]; trace back for the actual subsequence if needed | O(mn) time, O(mn) space (or O(n) with rolling row) |
Pattern: Two-pointer strings → 2D DP. Edit Distance, LCS, and Longest Palindromic Subsequence all use this exact structure. For 0/1 Knapsack, dimensions are items × capacity.
Interval DP — Sub-arrays / Partitioning (Burst Balloons, Matrix Chain, Palindrome Partition)
dp[i][j] = optimal answer for the sub-array/interval [i, j]. Fill by increasing interval length, trying every split point k.
| Step | Action (Matrix Chain Multiplication) | State After |
|---|---|---|
| 1 | dp[i][j] = min multiplications for chain from matrix i to j; base: dp[i][i]=0 | Diagonal zeroed |
| 2 | For each length L=2..n, for each i, j=i+L-1: try all split points k ∈ [i,j-1] | dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost) |
| 3 | Answer at dp[0][n-1] | O(n³) time, O(n²) space |
Pattern: Interval DP is identified by "minimum/maximum cost to reduce an interval" — burst balloons, stone merging, palindrome partitioning. The template is always: for length, for start, for split point.
Space Optimisation — O(n²) → O(n) → O(1)
Many DP tables only look back one or two rows; the previous rows can be discarded (rolling array). 1D DP often reduces to two variables.
| Step | Action | State After |
|---|---|---|
| 1 | Identify which previous states dp[i][j] depends on (row i-1 only? Column j-1?) | Dependency graph clear |
| 2 | Replace dp[i] with a 1D array; for 0/1 Knapsack iterate capacity backwards to prevent overwrite | Space: O(capacity) instead of O(n*capacity) |
| 3 | For Fibonacci/Climbing Stairs: two variables prev, curr suffice — O(1) space | Maximum compression achieved |
Tip: For 0/1 Knapsack space optimisation, iterate the capacity dimension backwards (from high to low) to ensure each item is counted at most once. Iterating forwards would allow an item to be picked multiple times (Unbounded Knapsack).
Common Mistakes:
- Wrong state definition: The state must fully capture the sub-problem. Missing a dimension (e.g. index, remaining capacity) leads to incorrect recurrences.
- Off-by-one in base cases: dp array size should be n+1 for 1-indexed problems. Initialising dp[0] incorrectly breaks the entire table.
- Greedy when DP is needed: If the choice at step i affects what's available at step i+k, greedy fails. Use DP when future choices depend on past decisions.
03
Section Three · Visuals
Diagrams & Walkthroughs
Fibonacci: Naive Recursion vs Memoization
Coin Change — Bottom-Up DP Table
LCS (Longest Common Subsequence) — 2D DP Table
04
Section Four · Code
Implementations
Quick-reference — Fibonacci top-down vs bottom-up. Click the button for full implementations of Coin Change, LCS, Knapsack, Edit Distance, and LIS.
// Fibonacci — Top-Down (Memoization) vs Bottom-Up // Top-Down O(n) time, O(n) space Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long res = fib(n-1) + fib(n-2);
memo.put(n, res);
return res;
}
// Bottom-Up O(n) time, O(1) space long fibDP(int n) {
if (n <= 1) return n;
long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) { long t = prev + curr; prev = curr; curr = t; }
return curr;
}
Dynamic Programming — Full Implementations
Java — Fibonacci, Coin Change, 0/1 Knapsack, LCS, Edit Distance, LIS
import java.util.*;
public class DynamicProgramming {
// ── Fibonacci (bottom-up O(1) space) ────────
public static long fib(int n) {
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long t = a + b; a = b; b = t; }
return b;
}
// ── Coin Change (min coins) ──────────────────
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
// ── 0/1 Knapsack ────────────────────────────
public static int knapsack(int[] weights, int[] values, int W) {
int n = weights.length;
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++)
for (int w = W; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[W];
}
// ── Longest Common Subsequence ───────────────
public static int lcs(String a, String b) {
int m = a.length(), n = b.length();
int[] dp = new int[n + 1]; // space-optimised: 1 row
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int cur = dp[j];
dp[j] = a.charAt(i-1) == b.charAt(j-1)
? prev + 1
: Math.max(dp[j], dp[j-1]);
prev = cur;
}
}
return dp[n];
}
// ── Edit Distance (Levenshtein) ──────────────
public static int editDistance(String a, String b) {
int m = a.length(), n = b.length();
int[] dp = new int[n + 1];
for (int j = 0; j <= n; j++) dp[j] = j;
for (int i = 1; i <= m; i++) {
int prev = dp[0];
dp[0] = i;
for (int j = 1; j <= n; j++) {
int cur = dp[j];
dp[j] = a.charAt(i-1) == b.charAt(j-1)
? prev
: 1 + Math.min(prev, Math.min(dp[j], dp[j-1]));
prev = cur;
}
}
return dp[n];
}
// ── Longest Increasing Subsequence (O(n log n)) ─
public static int lis(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int x : nums) {
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (tails.get(mid) < x) lo = mid + 1; else hi = mid;
}
if (lo == tails.size()) tails.add(x);
else tails.set(lo, x);
}
return tails.size();
}
}
Python — Fibonacci, Coin Change, Knapsack, LCS, Edit Distance, LIS
import bisect
# Fibonacci (bottom-up O(1) space)
def fib(n):
a, b = 0, 1
for _ in range(n): a, b = b, a + b
return a
# Coin Change (min coins)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 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
# 0/1 Knapsack
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for w, v in zip(weights, values):
for cap in range(W, w - 1, -1): # iterate backwards!
dp[cap] = max(dp[cap], dp[cap - w] + v)
return dp[W]
# Longest Common Subsequence
def lcs(a, b):
m, n = len(a), len(b)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
cur = dp[j]
dp[j] = prev + 1 if a[i-1] == b[j-1] else max(dp[j], dp[j-1])
prev = cur
return dp[n]
# Edit Distance
def edit_distance(a, b):
m, n = len(a), len(b)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]; dp[0] = i
for j in range(1, n + 1):
cur = dp[j]
dp[j] = prev if a[i-1] == b[j-1] else 1 + min(prev, dp[j], dp[j-1])
prev = cur
return dp[n]
# LIS — O(n log n) patience sorting
def lis(nums):
tails = []
for x in nums:
i = bisect.bisect_left(tails, x)
if i == len(tails): tails.append(x)
else: tails[i] = x
return len(tails)
JavaScript — Fibonacci, Coin Change, Knapsack, LCS, Edit Distance
// Fibonacci
function fib(n) {
let a = 0, b = 1;
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
// Coin Change
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++)
for (const c of coins)
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] === Infinity ? -1 : dp[amount];
}
// 0/1 Knapsack
function knapsack(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++)
for (let w = W; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[W];
}
// Longest Common Subsequence
function lcs(a, b) {
const [m, n] = [a.length, b.length];
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prev = 0;
for (let j = 1; j <= n; j++) {
const cur = dp[j];
dp[j] = a[i-1] === b[j-1] ? prev + 1 : Math.max(dp[j], dp[j-1]);
prev = cur;
}
}
return dp[n];
}
// Edit Distance
function editDistance(a, b) {
const [m, n] = [a.length, b.length];
const dp = Array.from({length: n+1}, (_, i) => i);
for (let i = 1; i <= m; i++) {
let prev = dp[0]; dp[0] = i;
for (let j = 1; j <= n; j++) {
const cur = dp[j];
dp[j] = a[i-1] === b[j-1] ? prev : 1 + Math.min(prev, dp[j], dp[j-1]);
prev = cur;
}
}
return dp[n];
}
C# — Fibonacci, Coin Change, Knapsack, LCS, Edit Distance
using System;
public class DynamicProgramming {
public static long Fib(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) (a, b) = (b, a + b);
return a;
}
public static int CoinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Array.Fill(dp, amount + 1); dp[0] = 0;
for (int a = 1; a <= amount; a++)
foreach (var c in coins)
if (c <= a) dp[a] = Math.Min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
public static int Knapsack(int[] w, int[] v, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < w.Length; i++)
for (int cap = W; cap >= w[i]; cap--)
dp[cap] = Math.Max(dp[cap], dp[cap - w[i]] + v[i]);
return dp[W];
}
public static int LCS(string a, string b) {
int m = a.Length, n = b.Length;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int cur = dp[j];
dp[j] = a[i-1] == b[j-1] ? prev + 1 : Math.Max(dp[j], dp[j-1]);
prev = cur;
}
}
return dp[n];
}
public static int EditDistance(string a, string b) {
int m = a.Length, n = b.Length;
int[] dp = new int[n + 1];
for (int j = 0; j <= n; j++) dp[j] = j;
for (int i = 1; i <= m; i++) {
int prev = dp[0]; dp[0] = i;
for (int j = 1; j <= n; j++) {
int cur = dp[j];
dp[j] = a[i-1] == b[j-1] ? prev : 1 + Math.Min(prev, Math.Min(dp[j], dp[j-1]));
prev = cur;
}
}
return dp[n];
}
}
05
Section Five · Complexity
Time & Space Complexity
| Problem | Time | Space (full) | Space (optimised) | Pattern |
|---|---|---|---|---|
| Fibonacci / Climbing Stairs | O(n) | O(n) | O(1) — two variables | 1D linear |
| House Robber / Max Subarray | O(n) | O(n) | O(1) | 1D linear |
| Coin Change (min coins) | O(n × amount) | O(amount) | O(amount) | Unbounded Knapsack |
| 0/1 Knapsack | O(n × W) | O(n × W) | O(W) — 1D reverse | 0/1 Subset |
| Longest Common Subsequence | O(mn) | O(mn) | O(min(m,n)) | 2D sequence |
| Edit Distance | O(mn) | O(mn) | O(n) | 2D sequence |
| LIS (O(n²) DP) | O(n²) | O(n) | — | 1D dependent |
| LIS (patience sort) | O(n log n) | O(n) | — | BS + tails array |
| Burst Balloons / Matrix Chain | O(n³) | O(n²) | — | Interval DP |
Time = States × Transition cost. For 1D DP: n states × O(1) transition = O(n). For 2D: mn states × O(1) = O(mn). For Interval DP: O(n²) intervals × O(n) split points = O(n³). Space can always be compressed if the recurrence only looks back a fixed number of rows.
Space Complexity Note
The key insight for space optimisation: identify which "previous" states dp[i][j] depends on. If only the previous row (dp[i-1][*]) is needed, replace the 2D array with a rolling 1D array. For 0/1 Knapsack, iterate the capacity dimension backwards so updates don't overwrite values still needed in the same pass.
06
Section Six · Decision Guide
When to Use Dynamic Programming
Use DP When
- Problem has optimal substructure (optimal solution ← optimal sub-solutions)
- Problem has overlapping subproblems (same sub-problem recurs)
- Problem asks min/max/count/exists for a combinatorial structure
- Brute force is exponential but the number of distinct states is polynomial
Avoid DP / Use Alternatives When
- Subproblems are independent → use Divide & Conquer (Merge Sort)
- A locally greedy choice is always globally optimal → use Greedy (activity selection)
- Problem requires tracking the full path/configuration, not just the value → Backtracking
- Input is a graph without DAG structure → graph algorithms (BFS/DFS/Dijkstra)
DP Pattern → Problem Mapping
| Pattern | State | Signature Problems |
|---|---|---|
| 1D Sequential | dp[i] | Climbing Stairs, House Robber, Max Subarray (Kadane) |
| Unbounded Knapsack | dp[amount] | Coin Change, Perfect Squares, Combination Sum IV |
| 0/1 Knapsack | dp[i][w] | Target Sum, Partition Equal Subset, Last Stone Weight II |
| Two-Sequence 2D | dp[i][j] | LCS, Edit Distance, Distinct Subsequences, Regex Match |
| Interval DP | dp[i][j] | Burst Balloons, Palindrome Partition, Stone Merge |
| State Machine | dp[i][state] | Best Time to Buy/Sell Stock (k transactions, cooldown) |
| DP on Trees | dp[node][…] | House Robber III, Diameter of Tree, Max Path Sum |
✓ DP Thinking Process: (1) Define state clearly. (2) Write the recurrence. (3) Identify base cases. (4) Determine fill order (bottom-up). (5) Optimise space if needed. Never skip step 1.
07
Section Seven · Interview Practice
LeetCode Problems
DP problems test your ability to identify the optimal substructure, define a clean DP state, and write a recurrence. Group problems by pattern to build intuition — not by difficulty.
- Easy#70 — Climbing Stairs — 1D DP: dp[i] = dp[i-1] + dp[i-2]. Identical to Fibonacci.
- Easy#198 — House Robber — 1D DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Non-adjacent selection.
- Easy#53 — Maximum Subarray — Kadane's: dp[i] = max(dp[i-1] + nums[i], nums[i]). O(1) space.
- Medium#322 — Coin Change — Unbounded knapsack; BFS also works for shortest path to amount.
- Medium#300 — Longest Increasing Subsequence — O(n²) DP or O(n log n) patience sorting with binary search.
- Medium#1143 — Longest Common Subsequence — Classic 2D DP; foundation for Edit Distance and Diff tools.
- Medium#416 — Partition Equal Subset Sum — 0/1 Knapsack: can we partition into two equal-sum subsets?
- Medium#152 — Maximum Product Subarray — Track both max and min dp values (negatives flip sign).
- Hard#72 — Edit Distance — 2D DP; three transitions: insert, delete, replace. Tracing back gives the actual edit sequence.
- Hard#312 — Burst Balloons — Interval DP; think "last balloon to burst" instead of first, for clean subproblem boundaries.
Interview Pattern: If you see "minimum cost", "maximum value", "number of ways", or "can it be done?" on a sequence or grid — DP is almost certainly the intended approach. Define the state first on paper, write the recurrence, then code. Rushing to code before defining the state is the #1 source of DP bugs in interviews.