Algorithms
Dynamic Programming Fundamentals
Break a problem into overlapping subproblems, solve each once, cache the result — turning exponential brute force into polynomial time. The most feared interview topic, but once you see the pattern, every DP problem is the same three steps: state, recurrence, base case.
Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.
01
Section One · Foundation
What is Dynamic Programming?
Dynamic programming is an optimisation technique that applies when a problem has two properties: overlapping subproblems (the same subproblem is solved multiple times in a naive recursive solution) and optimal substructure (the optimal solution to the problem contains optimal solutions to its subproblems). The technique works by solving each subproblem once and caching the result — subsequent calls look up the cached value instead of recomputing. This turns the exponential branching of naive recursion into polynomial time. There are two approaches: top-down (memoisation) — write the natural recursion and add a cache, and bottom-up (tabulation) — fill a table iteratively from the smallest subproblems upward. Both produce the same result; bottom-up is typically faster (no recursion overhead) and easier to optimise for space. Every DP problem reduces to three decisions: (1) what is the STATE — the parameters that uniquely identify a subproblem; (2) what is the RECURRENCE — how the current state relates to smaller states; (3) what is the BASE CASE — the smallest state with a known answer.
Analogy: Computing directions in a city. If someone asks you how to get from A to E, you figure out A→B→C→D→E. Then someone asks A to D — you already know the A→B→C→D part. Without caching, you recompute the entire route. With DP, you store each intermediate result: once you know the best route from A to C, you never recompute it — you just look it up. The "table" is your collection of solved sub-routes.
02
Section Two · Mental Model
How It Thinks
Naive recursion solves the same subproblem multiple times (overlapping subproblems)
▶
Exponential time — fib(n) has O(2ⁿ) calls because fib(k) is recomputed at every node that needs it
Cache (memo[n]) stores each subproblem's result after its first computation
▶
Every subproblem is solved at most once — n states × O(1) lookup = O(n) total. Exponential becomes polynomial.
Top-down (memoisation): write the recursion naturally, add a cache before returning
▶
Easiest to write — the recursive structure mirrors the recurrence directly. Only computes states that are actually needed (lazy evaluation).
Bottom-up (tabulation): fill a table from base cases upward using the recurrence
▶
No recursion overhead, no stack depth concern. Iterative loop over states in dependency order. Often allows space optimisation (only keep last 1–2 rows).
State = the minimum set of parameters that uniquely identify a subproblem
▶
1D state (one index i) → 1D DP array. 2D state (two indices i,j or index + capacity) → 2D DP table. Choosing the right state is the hardest part.
Space optimisation: if dp[i] only depends on dp[i-1] (or dp[i-1] and dp[i-2])
▶
Replace the entire array with 1–2 variables — O(n) space becomes O(1). For 2D, keep only the previous row — O(n×m) becomes O(m).
03
Section Three · Top-Down
Top-Down — Memoisation
Start from the original problem, recurse into subproblems, cache results. The code reads like the mathematical recurrence. Easiest to write — start with brute-force recursion, then add a memo array.
Fibonacci — Memoised
Pseudocode
memo = {}
function fib(n):
if n <= 1: return n // base case if n in memo: return memo[n] // cached? return it
memo[n] = fib(n - 1) + fib(n - 2) // compute + cache return memo[n] // O(n) time, O(n) space
The 3-Step Recipe for Top-Down DP
| Step | Question | Fibonacci Example |
|---|---|---|
| 1. State | What parameters define a subproblem? | n — the index |
| 2. Recurrence | How does current state relate to smaller states? | fib(n) = fib(n-1) + fib(n-2) |
| 3. Base case | Smallest state with a known answer? | fib(0)=0, fib(1)=1 |
Top-down is the "lazy" approach:
- It only computes subproblems that are actually needed.
- If the subproblem graph is sparse (many states exist but few are reachable), top-down avoids computing unnecessary states.
- Bottom-up computes ALL states in the table whether needed or not.
04
Section Four · Bottom-Up
Bottom-Up — Tabulation
Fill a table iteratively from the base cases upward. No recursion, no stack overflow risk. The iteration order must respect dependencies — each state should only depend on states already computed. Bottom-up is typically preferred in interviews for its simplicity and speed, and it enables space optimisation.
Fibonacci — Tabulated
Pseudocode
function fib(n):
dp = new int[n + 1]
dp[0] = 0, dp[1] = 1 // base cases for i = 2 to n:
dp[i] = dp[i - 1] + dp[i - 2] // recurrence return dp[n] // O(n) time, O(n) space
Space-Optimised (O(1) space)
function fib(n):
if n <= 1: return n
prev2 = 0, prev1 = 1 for i = 2 to n:
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1 // O(n) time, O(1) space
Bottom-up fills table left to right — each cell depends only on previous cells
Top-Down (Memoisation)
Recursive + Cache
- Write natural recursion first
- Add memo array/map
- Only computes reachable states
- Risk: stack overflow on deep recursion
- Easier to reason about
Bottom-Up (Tabulation)
Iterative + Table
- Fill table from base cases upward
- No recursion — no stack overflow
- Computes ALL states in the table
- Enables space optimisation
- Preferred in interviews
05
Section Five · 1D Problems
1D Dynamic Programming
The state is a single index or value — dp[i] represents the answer for the problem considering only the first i elements (or reaching position i). Most beginner DP problems are 1D.
Climbing Stairs (LC 70)
You can climb 1 or 2 stairs at a time. How many distinct ways to reach step n?
Analysis
// State: dp[i] = number of ways to reach step i // Recurrence: dp[i] = dp[i-1] + dp[i-2] // (arrive from step i-1 with 1 step, or from i-2 with 2 steps) // Base: dp[0] = 1, dp[1] = 1 // Answer: dp[n] // Time: O(n), Space: O(1) with optimisation
House Robber (LC 198)
Rob houses along a street — can't rob two adjacent houses. Maximise total loot.
Analysis
// State: dp[i] = max loot from houses 0..i // Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) // (skip house i, or rob it + best from 2 houses back) // Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) // Answer: dp[n-1] // Time: O(n), Space: O(1) with optimisation
The "take or skip" recurrence is the most common 1D DP pattern:
- At each element, you either take it (and add its value to the best achievable from a non-conflicting position) or skip it (and carry forward the best achievable so far).
- Climbing Stairs, House Robber, Coin Change, and Jump Game all follow this structure.
Coin Change (LC 322)
Given coin denominations and a target amount, find the minimum number of coins needed.
Analysis
// State: dp[amount] = min coins to make 'amount' // Recurrence: dp[a] = min(dp[a - coin] + 1) for each coin // (try using each coin — take the one that gives fewest total) // Base: dp[0] = 0 (zero coins for zero amount) // Init: dp[1..target] = ∞ (impossible until proven otherwise) // Answer: dp[target] (or -1 if still ∞) // Time: O(amount × coins), Space: O(amount)
06
Section Six · 2D Problems
2D Dynamic Programming
The state has two dimensions — dp[i][j] might represent "the answer considering the first i items with capacity j" (knapsack) or "the answer for substring s[i..j]" (interval DP) or "the answer at grid position (i,j)" (path problems). 2D DP is common in medium/hard interview problems.
Unique Paths (LC 62)
Count paths from top-left to bottom-right of an m×n grid, moving only right or down.
Analysis
// State: dp[i][j] = number of paths to reach cell (i, j) // Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] // (arrive from above or from the left) // Base: dp[0][j] = 1, dp[i][0] = 1 (only one way along edges) // Answer: dp[m-1][n-1] // Time: O(m×n), Space: O(n) with row optimisation
Longest Common Subsequence (LC 1143)
Find the length of the longest subsequence common to two strings.
Analysis
// State: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1] // Recurrence: // if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 // else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // Base: dp[0][j] = 0, dp[i][0] = 0 (empty string → LCS = 0) // Answer: dp[m][n] // Time: O(m×n), Space: O(n) with row optimisation
LCS table for "ABCDE" and "ACE" — dp[5][3] = 3
Space optimisation for 2D DP:
- If dp[i][j] only depends on row i-1 and row i, you only need to keep two rows (or even one row, filling right-to-left).
- This reduces O(m×n) space to O(n).
- For LCS:
int[] prev = new int[n+1], curr = new int[n+1]— swap after each row.
07
Section Seven · Classic Patterns
DP Pattern Families
| Pattern | State | Recurrence Shape | Examples |
|---|---|---|---|
| Linear (1D) | dp[i] = answer for first i elements | dp[i] = f(dp[i-1], dp[i-2], ...) | Fibonacci, Stairs, House Robber |
| Knapsack | dp[i][w] = best value with items 0..i, capacity w | dp[i][w] = max(skip, take + dp[i-1][w-wt]) | 0/1 Knapsack, Coin Change, Partition Equal Subset |
| Grid paths | dp[i][j] = answer at cell (i,j) | dp[i][j] = f(dp[i-1][j], dp[i][j-1]) | Unique Paths, Min Path Sum |
| String matching | dp[i][j] = answer for s1[0..i], s2[0..j] | match → diagonal + 1; no match → max(up, left) | LCS, Edit Distance, Interleaving |
| Interval | dp[i][j] = answer for subarray i..j | dp[i][j] = f(dp[i][k], dp[k+1][j]) for k in i..j | Burst Balloons, Matrix Chain |
| Subsequence | dp[i] = longest ending at index i | dp[i] = max(dp[j]+1) for j < i where arr[j] < arr[i] | LIS, Max Sum Increasing Subseq |
Common Mistake: Confusing "subarray" with "subsequence." A subarray is contiguous (sliding window handles this). A subsequence is not contiguous (DP handles this). "Maximum Subarray" (LC 53, Kadane's) is linear — NOT classic DP. "Longest Increasing Subsequence" (LC 300) IS DP because elements can be non-contiguous.
08
Section Eight · Implementation
Build It Once
Build each classic DP pattern once. The hardest part is identifying the state and recurrence — once you have those, the code is mechanical.
Java — DP core patterns
// 1. Climbing Stairs — O(n) time, O(1) space int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b; a = b; b = c;
}
return b;
}
// 2. House Robber — O(n) time, O(1) space int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1; prev1 = curr;
}
return prev1;
}
// 3. Coin Change — O(amount × coins) time 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];
}
Dynamic Programming — Full Implementation
Java — Classic DP implementations
import java.util.*;
public class DynamicProgramming {
// ═══ 1. Climbing Stairs ══════════════════ O(n), O(1) static int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}
// ═══ 2. House Robber ═════════════════════ O(n), O(1) static int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1; prev1 = curr;
}
return prev1;
}
// ═══ 3. Coin Change ═════════════════════ O(amount×coins) 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];
}
// ═══ 4. Longest Increasing Subsequence ══ O(n²) / O(n log n) static int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
return max;
}
// ═══ 5. Unique Paths (grid) ═════════════ O(m×n), O(n) static int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j - 1];
return dp[n - 1];
}
// ═══ 6. Longest Common Subsequence ══════ O(m×n), O(n) static int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[] prev = new int[n + 1], curr = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
curr[j] = prev[j-1] + 1;
else
curr[j] = Math.max(prev[j], curr[j-1]);
}
int[] tmp = prev; prev = curr; curr = tmp;
Arrays.fill(curr, 0);
}
return prev[n];
}
// ═══ 7. 0/1 Knapsack ═══════════════════ O(n×W), O(W) static int knapsack(int[] weights, int[] values, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < weights.length; i++)
for (int w = W; w >= weights[i]; w--) // iterate RIGHT to LEFT
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[W];
}
// ═══ 8. Edit Distance ═══════════════════ O(m×n) static int minDistance(String w1, String w2) {
int m = w1.length(), n = w2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (w1.charAt(i-1) == w2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Math.min(dp[i-1][j-1],
Math.min(dp[i-1][j], dp[i][j-1]));
}
return dp[m][n];
}
// ═══ Main ═══════════════════════════════════ public static void main(String[] args) {
System.out.println("Stairs(5): " + climbStairs(5)); // 8 System.out.println("Rob: " + rob(new int[]{2,7,9,3,1})); // 12 System.out.println("Coins: " + coinChange(new int[]{1,5,10}, 27)); // 5 System.out.println("LIS: " + lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // 4 System.out.println("Paths(3,7): " + uniquePaths(3, 7)); // 28 System.out.println("LCS: " + longestCommonSubsequence("abcde", "ace")); // 3 System.out.println("Edit: " + minDistance("horse", "ros")); // 3
}
}
Python — DP implementations
# ═══ 1. Climbing Stairs ══════════════════ O(n), O(1) def climb_stairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
# ═══ 2. House Robber ═════════════════════ O(n), O(1) def rob(nums):
prev2 = prev1 = 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
# ═══ 3. Coin Change ═════════════════════ O(amount×coins) def coin_change(coins, amount):
dp = [0] + [float('inf')] * amount
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
# ═══ 4. LIS ═════════════════════════════ O(n²) def length_of_lis(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# ═══ 5. Unique Paths ════════════════════ O(m×n), O(n) def unique_paths(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]
# ═══ 6. LCS ═════════════════════════════ O(m×n) def lcs(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]
# ═══ 7. 0/1 Knapsack ═══════════════════ O(n×W) def knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
# ═══ 8. Edit Distance ═══════════════════ O(m×n) def min_distance(w1, w2):
m, n = len(w1), len(w2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if w1[i-1] == w2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[m][n]
# Demo
print(climb_stairs(5)) # 8
print(rob([2,7,9,3,1])) # 12
print(coin_change([1,5,10], 27)) # 5
print(length_of_lis([10,9,2,5,3,7,101,18])) # 4
print(unique_paths(3, 7)) # 28
print(lcs("abcde", "ace")) # 3
print(min_distance("horse", "ros")) # 3
09
Section Nine · Java Reference
Use It In Java
IN JAVA — DP Idioms & Patterns
1D table
int[] dp = new int[n + 1]; — most common, 0-indexed or 1-indexed 2D table
int[][] dp = new int[m + 1][n + 1]; — string/grid problems Memo map
Map<String, Integer> memo = new HashMap<>(); — multi-key states | Idiom | Use case | Note |
|---|---|---|
Arrays.fill(dp, value) | Initialise DP array | Use Integer.MAX_VALUE for min problems, 0 for count problems |
dp[0] = base_value | Base case | dp[0] = 0 for coin change, dp[0] = 1 for path counting |
Math.max / Math.min | Recurrence | Maximise or minimise at each state |
int prev2, prev1, curr | Space optimisation | Replace dp array when only 2 previous values needed |
for (w = W; w >= wt; w--) | 0/1 Knapsack (1D) | Iterate right-to-left to avoid using same item twice |
int[] prev, curr; swap | 2D → 1D space opt | Keep only the previous row for 2D problems |
⚠ Gotcha: In 0/1 Knapsack with a 1D array, iterate the capacity loop RIGHT to LEFT (
for w = W down to wt). This ensures each item is used at most once. If you iterate left to right, the same item can be used multiple times — that's the unbounded knapsack variant, not 0/1.
⚠ Gotcha: When using
Integer.MAX_VALUE as the "impossible" sentinel in min problems (like Coin Change), adding 1 to it causes integer overflow → wraps to Integer.MIN_VALUE. Guard with: if (dp[a-c] != Integer.MAX_VALUE) dp[a] = min(dp[a], dp[a-c]+1). Or use amount + 1 as sentinel instead.
10
Section Ten · Practice
Problems To Solve
DP interview problems are pattern-based — once you've solved one problem in a family, others in the same family are variations. Start with 1D problems (Climbing Stairs, House Robber), then move to Knapsack variants (Coin Change, Partition Equal Subset), then string DP (LCS, Edit Distance). The hardest step is always defining the state — once you have the state and recurrence, the code is mechanical.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | 1D linear | Climbing Stairs — LC 70 | dp[i] = dp[i-1] + dp[i-2]. Identical to Fibonacci. Space-optimise to O(1) with two variables. |
| Medium | 1D take/skip | House Robber — LC 198 | dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Take or skip each house. Space-optimise to O(1). |
| Medium | knapsack | Coin Change — LC 322 | dp[a] = min(dp[a-coin]+1) for each coin. Unbounded knapsack variant. Sentinel: amount+1 for impossible. |
| Medium | subsequence | Longest Increasing Subsequence — LC 300 | dp[i] = max(dp[j]+1) for j < i where nums[j] < nums[i]. O(n²). Binary search variant achieves O(n log n). |
| Medium | string | Longest Common Subsequence — LC 1143 | dp[i][j] = match → diagonal+1, else max(up, left). Space-optimise with two rows. |
| Medium | string | Edit Distance — LC 72 | dp[i][j] = min cost to convert s1[0..i] to s2[0..j]. Three operations: insert, delete, replace. Match → free (diagonal). |
Interview Pattern:
- When you see "count the number of ways," "minimum/maximum cost," "can you reach / partition / make amount X" — think DP.
- The three steps: (1) Define the STATE — what parameters uniquely identify a subproblem. (2) Write the RECURRENCE — how dp[i] depends on smaller states. (3) Set the BASE CASE — the smallest state with a known answer.
- Then code it bottom-up with a for loop. Optimise space if dp[i] only needs the previous 1–2 values.
→ See Dynamic Programming — 1D problems with full solutions
→ See Dynamic Programming — 2D / Advanced problems with full solutions