Dynamic Programming
Dynamic programming (DP) is the algorithm design technique that strikes fear into interviewees. It shouldn't. DP is simply recursion without redundancy — you solve each subproblem once, store the result, and reuse it. The hard part is seeing that a problem has the right structure for DP. Once you can identify the state, the transition, and the base case, the code writes itself.
This page is the overview lesson of Module 6 — Dynamic Programming in DSA: Zero to Mastery, and it is also the module's landing page. The first part (down to "When to Use DP") is the map: what the twenty lessons and the capstone cover, why they come in this order, and a table that tells you which DP family a problem belongs to from the words in its statement. The second part is a fast tour of the classic problems — Fibonacci, climbing stairs, coin change, LIS, house robber, LCS, edit distance, knapsack, matrix chain, word break — each with its state, recurrence and code, and a pointer to the lesson that goes deeper.
Previous module: Module 5 · Paradigms (recursion and backtracking, divide and conquer, greedy, bit manipulation, randomized algorithms). Next: Module 7 · String Algorithms.
How this module is organised
Module 6 has one overview (this page), twenty lessons and a capstone. It starts with the one framework every DP uses, then works through the families of DP grouped by the shape of the state — a position in a line, a pair of positions, a range, a tree node, a set, a digit position — then the families grouped by what is computed (counts, probabilities, game values), and ends with how to make a DP fast and how to debug one.
| # | Lesson | What you will be able to do | Minutes |
|---|---|---|---|
| 1 | Dynamic Programming (Overview) | Recognise a DP problem, name its family, and recall the state and recurrence of the ten classic problems. | 45 |
| 2 | DP Foundations | Derive any DP with five questions (state, transition, base, answer, order), choose memoization or tabulation, reconstruct the answer and roll arrays. | 60 |
| 3 | 1-D DP | Solve linear problems (stairs, robbers, decoding, maximum subarray, stock trading) with dp[i] and small state machines. | 50 |
| 4 | Knapsack | Solve 0/1, unbounded, bounded and multi-dimensional knapsack, subset sum and coin change, and explain pseudo-polynomial time. | 55 |
| 5 | Sequence DP | Compute LIS in , LCS, edit distance and alignments, and reconstruct them (including in linear space). | 60 |
| 6 | String DP | Fill prefix-by-prefix tables for word break, wildcard and regex matching, distinct subsequences, palindrome partitioning and interleaving. | 60 |
| 7 | Grid & Path DP | Count and optimise paths on grids, fill backwards when the state is simpler at the goal, and synchronise two walkers. | 55 |
| 8 | Interval DP | Solve range problems (matrix chain, burst balloons, optimal BST, palindromes) by choosing the last operation in a range. | 55 |
| 9 | Partition DP | Cut a sequence into contiguous groups optimally (painters, splitting arrays, text justification). | 45 |
| 10 | Tree DP | Compute per-subtree states in post-order, and answer "for every root" questions with rerooting. | 55 |
| 11 | DAG DP | See every DP as a path problem on a DAG; longest paths, path counts and memoised DFS on implicit DAGs. | 45 |
| 12 | Bitmask DP | Use a subset as the state for : travelling salesman, assignment, Hamiltonian paths. | 55 |
| 13 | SOS DP | Sum (or OR, max) over all submasks of every mask in instead of . | 45 |
| 14 | Digit DP | Count integers in with a digit property using the (position, tight, property) state. | 50 |
| 15 | Broken-Profile DP | Tile narrow grids with dominoes and shapes by carrying a bitmask profile across cells. | 50 |
| 16 | Counting DP | Count arrangements modulo a prime without double counting, and combine DP with combinatorics. | 55 |
| 17 | Probability DP | Compute probabilities and expected values over random processes, including states that loop. | 50 |
| 18 | Game DP | Solve two-player optimal-play games with win/lose states and score differences; connect to Sprague-Grundy. | 50 |
| 19 | Matrix Exponentiation | Turn a fixed-size linear recurrence into a matrix power and evaluate it for up to . | 45 |
| 20 | DP Optimizations | Speed up transitions with monotonic queues, convex hull trick, divide-and-conquer DP, Knuth and Aliens tricks. | 75 |
| 21 | DP Debugging & How to Find the State | Find a state with a checklist and a dimension audit, recognise the common DP bugs, and stress-test a DP against brute force. | 50 |
| — | Capstone: A Diff Tool and a Spell-Checker with DP | Build an LCS line diff with unified output, edit-distance spelling suggestions, minimum-raggedness line breaking, and benchmark the full table against two rows. | 180–240 |
The whole module is about 18 hours of reading and tracing plus the capstone; the practice ladders roughly double it. It is the longest module in the course because DP is less a single algorithm than a way of thinking, and the only way to learn it is many problems.
Module 6 at a glance
Dynamic programming solves a problem by solving smaller instances of the same problem, storing each answer, and combining stored answers — so that every distinct subproblem is solved exactly once. It applies when the subproblems overlap (the same smaller question comes up many times) and when the best answer is built from best answers to subproblems (optimal substructure). Every DP is specified by the same five things: the state (what a subproblem is), the transition (how to compute a state from smaller ones), the base cases, the answer state, and an order in which to compute the states. Learning DP is mostly learning to find the state; everything else follows from it.
What this module covers
Twenty lessons after this overview, in six arcs, and a capstone.
Arc 1 — the framework. DP Foundations gives the five questions, memoization versus tabulation (with the recursion-depth limits of each language), reconstruction, rolling arrays, and ten classic problems derived the same way. 1-D DP is the simplest state shape, a position in a line, including small per-position state machines. Knapsack adds a resource budget as a second dimension and introduces pseudo-polynomial time.
Arc 2 — two indices. Sequence DP (LIS, LCS, edit distance, alignment), String DP (matching and segmenting strings) and Grid & Path DP (paths on boards) all fill a two-dimensional table where each cell reads its neighbours. They are the same idea seen from three angles: two prefixes, a prefix of text and a prefix of pattern, a row and a column.
Arc 3 — structure-shaped states. Interval DP uses a range as the state and splits on the last operation; Partition DP cuts a line into groups; Tree DP uses a subtree; DAG DP makes explicit that every DP is a path computation on the DAG of its subproblems, linking back to Topological Sort.
Arc 4 — compressed states. When the past must be remembered as a set, Bitmask DP stores it in an integer (), and SOS DP aggregates over all subsets fast. Digit DP walks the digits of a number with a "tight" flag; Broken-Profile DP walks a grid cell by cell with a bitmask frontier.
Arc 5 — what you compute. Counting DP (counts modulo a prime, avoiding double counting), Probability DP (expected values), Game DP (optimal play) and Matrix Exponentiation (linear recurrences for astronomically large ).
Arc 6 — fast and correct. DP Optimizations keeps the state and speeds up the transition (monotonic deque, convex hull trick, divide and conquer, Knuth). DP Debugging & How to Find the State is the toolkit for when you are stuck: a state-finding checklist, a dimension audit, a bug catalogue, and a stress-test harness in four languages.
Capstone. A Diff Tool and a Spell-Checker with DP: an LCS-based line diff with unified output, edit-distance spelling suggestions with a BK-tree, minimum-raggedness line breaking (partition DP), and a benchmark of the full table against the two-row version — deriving each state, verifying it against a brute force with the harness from the debugging lesson, and measuring what each optimisation buys.
Why in this order
Foundations first, because the framework is the subject. Every later lesson is "the five questions, with a new kind of state". If the framework is solid, a new family is one new idea; if not, every family feels like a list of tricks to memorise.
1-D, then knapsack, then two indices. Each step adds exactly one dimension. 1-D DP teaches the "last decision" transition with a one-number state. Knapsack adds a budget dimension and the first loop-direction subtlety (0/1 versus unbounded). Sequence, string and grid DPs then add a second position, and with it the 2-D table you can draw and trace by hand. Sequence DP comes before String DP because string matching (wildcards, regex) is LCS-style alignment with richer transitions; Grid DP closes the arc because it is the same table with the strings removed, and its "fill backwards" idea is needed next.
Intervals before partitions before trees before DAGs. Interval DP introduces splitting a range at an interior point, which partition DP specialises (split a prefix into groups) and tree DP generalises (split at a node's children). DAG DP comes last in the arc because it is the unifying view: once you have seen four state shapes, "they are all paths in a subproblem DAG" is an insight rather than an abstraction.
Compressed states after structural ones. Bitmask DP needs comfort with bit manipulation and with states that are not positions. SOS DP is an optimisation of bitmask aggregation, so it follows directly. Digit DP and broken-profile DP both carry a small "frontier" (tight flag, profile mask) along a walk, which is easiest to accept after bitmasks.
What-you-compute last among the families. Counting, probability and game DPs reuse every state shape above; they change the values (sums modulo , expectations, win/lose) rather than the states. Matrix exponentiation follows counting because it is a counting DP with a fixed-size state run for steps.
Optimisations and debugging at the end — but read debugging early. Optimisations only make sense once you have correct DPs that are too slow. The debugging lesson is placed last because its examples come from every family, but it is written to be read right after DP Foundations and revisited whenever you are stuck.
flowchart TD
M5["Module 5 · Paradigms"] --> OV["DP overview"]
OV --> FND["DP Foundations"]
FND --> ONE["1-D DP"]
FND --> DBG["DP Debugging"]
ONE --> KS["Knapsack"]
ONE --> SEQ["Sequence DP"]
SEQ --> STR["String DP"]
SEQ --> GRID["Grid DP"]
SEQ --> INT["Interval DP"]
INT --> PART["Partition DP"]
INT --> TREE["Tree DP"]
GRID --> DAG["DAG DP"]
TREE --> DAG
KS --> BM["Bitmask DP"]
BM --> SOS["SOS DP"]
ONE --> DIG["Digit DP"]
BM --> BP["Broken-Profile DP"]
KS --> CNT["Counting DP"]
CNT --> PROB["Probability DP"]
DAG --> GAME["Game DP"]
CNT --> MAT["Matrix Exponentiation"]
PART --> OPT["DP Optimizations"]
KS --> OPT
OPT --> CAP["Capstone"]
DBG --> CAP
STR --> CAP
CAP --> M7["Module 7 · String Algorithms"]
Arrows mean "read this first". DP Debugging hangs off Foundations on purpose: read it early. Digit DP needs only 1-D thinking plus the "tight" idea; Game DP is easiest after DAG DP because a game's positions form a DAG (or, with cycles, need the retrograde analysis covered there).
Which DP family?
The literal words in a problem statement are the fastest guide to the state. Match the first row that fits; if none does, run the checklist in DP Debugging.
| If the problem says or has… | Family | Typical state | Lesson |
|---|---|---|---|
| "number of ways to climb / reach / decode", decisions along a line looking back a fixed distance | 1-D DP | dp[i] | 1-D DP |
| "cannot pick adjacent", "cooldown", "at most transactions" | 1-D DP with a small state machine | dp[i][state] | 1-D DP |
| Items with weight and value, a capacity, a target sum, "each at most once" / "unlimited" | Knapsack | dp[i][c] or dp[c] | Knapsack |
| "subsequence", "longest common", "edit / insert / delete / replace", "align" | Sequence DP | dp[i][j] over prefixes | Sequence DP |
"matches pattern with * and ?/.", "segment into words", "interleave", "palindrome partition" | String DP | prefix of text × prefix of pattern | String DP |
| A grid, "only right or down", "minimum path sum", "number of paths with obstacles" | Grid DP | dp[r][c] | Grid & Path DP |
| "merge adjacent piles", "burst", "parenthesise", "cost depends on both neighbours", "remove from either end" | Interval DP | dp[l][r] | Interval DP |
| "split the array into contiguous parts", "minimise the largest part", "line breaks" | Partition DP | dp[k][i] | Partition DP |
| A tree, "no parent and child both chosen", "subtree", "for every node as root" | Tree DP | dp[v][flag], rerooting | Tree DP |
| "longest path in a DAG", "number of paths", dependencies, "strictly increasing moves in a matrix" | DAG DP | dp[v] in topological order | DAG DP |
| , "visit every city", "assign each person a task", "each used once" | Bitmask DP | dp[mask] or dp[mask][last] | Bitmask DP |
| "for every mask, sum over its submasks / supersets", AND/OR pair counting | SOS DP | f[mask] | SOS DP |
| "how many integers in " with a digit condition, up to | Digit DP | (pos, tight, …) | Digit DP |
| Tile an board with dominoes or trominoes, one side or so | Broken-profile DP | (cell, profile) | Broken-Profile DP |
| "count … modulo ", permutations or arrangements with constraints | Counting DP | counts with % | Counting DP |
| "expected number of steps", "probability that", dice, random walks | Probability DP | E[state], P[state] | Probability DP |
| "two players", "both play optimally", "who wins", "maximise your score minus theirs" | Game DP | win[state], score difference | Game DP |
| A linear recurrence and up to ; "number of walks of length " | Matrix exponentiation | transition matrix | Matrix Exponentiation |
| Correct or DP, limits demand faster; transition is a min over a window or a line | DP optimisation | same state, faster transition | DP Optimizations |
| Moves in all directions, cycles, non-negative weights | Not DP — shortest path | dist[v] | Shortest Paths |
| "list all solutions" | Not DP — backtracking (DP can only count them) | — | Backtracking & Recursion |
| A provably safe local choice (exchange argument works) | Not DP — greedy | — | Greedy Algorithms |
Prerequisites
From Module 0: Recursion & Mathematical Induction — every DP starts as a recursion and every DP proof is an induction over the order of computation — and Complexity Analysis, because you will estimate states × transitions before writing code. Testing & Debugging Algorithms supplies the brute-force comparator habit that the debugging lesson builds on. From Module 1: Prefix Sums and the monotonic deque, both reused to speed up transitions. From Module 4: Topological Sort, the formal version of "an order in which to compute the states". From Module 5: Backtracking & Recursion (DP is backtracking that remembers), Greedy Algorithms (and when greedy fails, which is often how you know you need DP) and Bit Manipulation for the bitmask lessons.
You need one of Python 3.12+, Java 21, C++17 or later, or TypeScript (Node 22+). Every canonical implementation in the module is given in all four and checks itself.
How to study this module
Write the state sentence before any code. "dp[i][c] = the best value using the first i items with capacity at most c." If you cannot write it in one sentence, you are not ready to code — run the state-finding checklist.
Brute force first, then memoize, then tabulate. The brute-force recursion shows you the state (its parameters), and it is the oracle you will stress-test against. This is slower for the first few problems and much faster from then on.
Trace a small table by hand. Every lesson has a trace table computed by a script. Cover it, fill the table yourself for the small input, then compare. The first cell where you disagree is a misunderstanding caught before it became a bug.
Learn families, not problems. After each problem, write one line: "family, state, transition". The Which DP family? table above is the index those lines go into. Interviews reuse families far more than problems.
Two passes through the practice ladders. The first half of each ladder as you read; the hard tail after you have finished the arc. DP skill grows with the number of states you have designed, not with the number of solutions you have read.
Start with DP Foundations, then follow the table. Previous module: Module 5 · Paradigms. Next module: String Algorithms. Course map: DSA: Zero to Mastery.
A fast tour of the classic problems
The rest of this page is the original quick tour: the two DP properties, memoization versus tabulation, the four-question framework, and the classic 1-D, 2-D and interval problems with code. Each section points to the lesson that treats it in depth: DP Foundations for the framework, 1-D DP for stairs and robbers, Knapsack for coin change and knapsack, Sequence DP for LIS, LCS and edit distance, Interval DP for matrix chain, and String DP for word break.
When to Use DP
A problem is a DP candidate when it has two properties:
- Optimal substructure: The optimal solution contains optimal solutions to subproblems
- Overlapping subproblems: The same subproblems are solved multiple times
graph TD
F5["fib(5)"] --> F4["fib(4)"]
F5 --> F3a["fib(3)"]
F4 --> F3b["fib(3)"]
F4 --> F2a["fib(2)"]
F3a --> F2b["fib(2)"]
F3a --> F1a["fib(1)"]
F3b --> F2c["fib(2)"]
F3b --> F1b["fib(1)"]
style F3a fill:#f96
style F3b fill:#f96
style F2a fill:#ff0
style F2b fill:#ff0
style F2c fill:#ff0
Fibonacci without memoization: fib(3) is computed twice, fib(2) three times. This exponential redundancy is what DP eliminates.
Top-Down (Memoization) vs Bottom-Up (Tabulation)
Top-Down: Memoization
Start from the main problem, recurse into subproblems, cache results.
TypeScript:
function fibMemo(n: number, memo = new Map<number, number>()): number {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n)!;
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
Python:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
Bottom-Up: Tabulation
Start from the smallest subproblems, build up to the answer iteratively.
TypeScript:
function fibTab(n: number): number {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space-optimized: O(1) instead of O(n)
function fibOptimized(n: number): number {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
Python:
def fib_tab(n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def fib_optimized(n: int) -> int:
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
Comparison
| Top-Down (Memoization) | Bottom-Up (Tabulation) | |
|---|---|---|
| Approach | Recursive + cache | Iterative + table |
| Solves all subproblems? | Only what's needed | All subproblems |
| Stack overflow risk | Yes (deep recursion) | No |
| Space optimization | Harder | Easier (rolling array) |
| Thinking style | Natural (start from goal) | Requires ordering subproblems |
TIP
Start with top-down memoization when solving a new problem — it maps directly to the recursive structure and is easier to reason about. Convert to bottom-up for production code where stack overflow is a concern or space optimization is needed.
The DP Framework
For any DP problem, answer these four questions:
- State: What information defines a subproblem? → This becomes your DP array dimensions
- Transition: How does a state relate to smaller states? → This is your recurrence relation
- Base case: What are the trivial subproblems? → Initialization of your DP array
- Answer: Which state contains the final answer?
A fifth question: order
DP Foundations adds Order — in which sequence to compute the states so that every state's inputs are ready — and applies all five questions to ten classic problems with trace tables and code in four languages. When the state will not come, use the checklist in DP Debugging & How to Find the State.
1D Dynamic Programming
Climbing Stairs
Problem: You can climb 1 or 2 steps at a time. How many ways to reach the top of stairs?
State: dp[i] = number of ways to reach step
Transition: (come from one step or two steps below)
TypeScript:
function climbStairs(n: number): number {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
Python:
def climb_stairs(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
Complexity: time, space.
Coin Change
Problem: Given coin denominations and a target amount, find the minimum number of coins needed.
State: dp[amount] = minimum coins to make amount
Transition: for each coin
TypeScript:
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a && dp[a - coin] + 1 < dp[a]) {
dp[a] = dp[a - coin] + 1;
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
Python:
def coin_change(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Complexity: time, space.
Longest Increasing Subsequence (LIS)
Problem: Find the length of the longest strictly increasing subsequence.
DP approach:
State: dp[i] = length of LIS ending at index
Transition:
approach with patience sorting:
Python:
import bisect
def length_of_lis(nums: list[int]) -> int:
# tails[i] = smallest tail element for increasing subsequence of length i+1
tails: list[int] = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
TypeScript:
function lengthOfLIS(nums: number[]): number {
const tails: number[] = [];
for (const num of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < num) lo = mid + 1;
else hi = mid;
}
tails[lo] = num;
if (lo === tails.length) tails.push(num);
else tails[lo] = num;
}
return tails.length;
}
Complexity: time, space.
House Robber
Problem: Rob houses along a street; cannot rob two adjacent houses. Maximize total loot.
Python:
def rob(nums: list[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
2D Dynamic Programming
Longest Common Subsequence (LCS)
Problem: Find the length of the longest common subsequence between two strings.
State: dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]
Transition:
TypeScript:
function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length;
const n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
Python:
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
Complexity: time, space (optimizable to with rolling array).
Edit Distance (Levenshtein Distance)
Problem: Minimum operations (insert, delete, replace) to transform one string into another.
State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]
Transition:
TypeScript:
function minDistance(word1: string, word2: string): number {
const m = word1.length;
const n = word2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Base cases
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // delete
dp[i][j - 1], // insert
dp[i - 1][j - 1] // replace
);
}
}
}
return dp[m][n];
}
Python:
def min_distance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
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 word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
Complexity: time, space.
Production Use Case
Edit distance is used in spell checkers, DNA sequence alignment, diff tools, and fuzzy search. It's not just an interview problem — it's a foundational algorithm in bioinformatics and text processing.
0/1 Knapsack
Problem: Given items with weights and values and a capacity, maximize total value without exceeding the weight limit. Each item can be used at most once.
State: dp[i][w] = max value using first items with capacity
Transition:
Python:
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # don't take item i
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
# Space-optimized: single row, iterate capacity in reverse
def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1): # reverse to avoid reuse
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
Complexity: time and space ( space optimized), where is the capacity. This is pseudo-polynomial — polynomial in the value of , not the number of bits needed to represent it.
Interval DP
Problems where the state is defined over a contiguous range.
Matrix Chain Multiplication
Problem: Find the most efficient way to multiply a chain of matrices.
Python:
def matrix_chain_order(dims: list[int]) -> int:
"""dims[i-1] x dims[i] is the dimension of matrix i."""
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
# l is the chain length
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n - 1]
Complexity: time, space.
State Transition Thinking Framework
When you encounter a new DP problem, follow this systematic process:
graph TD
A["1. Identify the choices<br/><small>What decisions do you make at each step?</small>"] --> B["2. Define the state<br/><small>What information captures a subproblem?</small>"]
B --> C["3. Write the recurrence<br/><small>How does current state relate to smaller states?</small>"]
C --> D["4. Identify base cases<br/><small>What are the trivial subproblems?</small>"]
D --> E["5. Determine computation order<br/><small>Which subproblems must be solved first?</small>"]
E --> F["6. Extract the answer<br/><small>Which state contains the final result?</small>"]
Example Walkthrough: Word Break
Problem: Given a string and a dictionary, determine if the string can be segmented into dictionary words.
- Choices: At each position, try every possible word from the dictionary that starts there
- State:
dp[i]= cans[0..i-1]be segmented? - Recurrence:
dp[i] = any(dp[j] and s[j:i] in wordDict for j in range(i)) - Base case:
dp[0] = True(empty string) - Order: Left to right
- Answer:
dp[len(s)]
Python:
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]
Common DP Patterns
| Pattern | Examples | State Hint |
|---|---|---|
| Linear sequence | Climbing stairs, house robber, LIS | dp[i] indexed by position |
| Two sequences | LCS, edit distance | dp[i][j] two indices |
| Knapsack / subset | 0/1 knapsack, subset sum, coin change | dp[i][capacity] or dp[capacity] |
| Interval | Matrix chain, burst balloons, palindrome partition | dp[i][j] for range |
| Grid | Unique paths, min path sum | dp[row][col] |
| Bitmask | Traveling salesman, set cover | dp[mask] where mask is a bitmask |
| String partition | Word break, palindrome partitioning | dp[i] or dp[i][j] |
Common Mistakes
- Not handling base cases correctly: Off-by-one errors in DP indices are the #1 source of bugs
- Wrong computation order: In bottom-up, you must fill states that are dependencies first
- Forgetting to consider all transitions: Missing a case in the recurrence relation leads to wrong answers
- Confusing 0/1 knapsack with unbounded: In 0/1 knapsack, iterate capacity in reverse; in unbounded, iterate forward
Space Optimization
Many 2D DP problems only depend on the previous row, allowing space instead of :
Before (LCS with space):
dp = [[0] * (n + 1) for _ in range(m + 1)]
After (LCS with space):
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, [0] * (n + 1)
Practice Problems
| Problem | Pattern | Difficulty |
|---|---|---|
| Climbing Stairs | 1D linear | Easy |
| House Robber | 1D linear | Medium |
| Coin Change | 1D knapsack | Medium |
| Longest Increasing Subsequence | 1D + binary search | Medium |
| Word Break | 1D string partition | Medium |
| Longest Common Subsequence | 2D two-sequence | Medium |
| Edit Distance | 2D two-sequence | Medium |
| 0/1 Knapsack | 2D subset | Medium |
| Unique Paths | 2D grid | Medium |
| Longest Palindromic Substring | 2D interval | Medium |
| Burst Balloons | Interval DP | Hard |
| Regular Expression Matching | 2D two-sequence | Hard |
Further Reading
- Backtracking & Recursion — DP often starts as a brute-force recursion that you optimize
- Graphs — shortest path algorithms are DP in disguise
- Arrays & Strings — many string DP problems build on array techniques
- Sorting & Searching — binary search in LIS optimization
Try It Yourself
Problem 1: How many distinct ways can you climb a staircase of 5 steps, taking 1 or 2 steps at a time?
Solution
Use the climbing stairs recurrence: .
- dp[1] = 1, dp[2] = 2
- dp[3] = dp[2] + dp[1] = 3
- dp[4] = dp[3] + dp[2] = 5
- dp[5] = dp[4] + dp[3] = 8
Problem 2: Given coins [1, 3, 4] and amount 6, find the minimum number of coins needed.
Solution
Build the DP table: .
- dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1
- dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(2, 3, 2) = 2
- dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2 Answer: 2 coins (3 + 3)
Problem 3: Find the Longest Common Subsequence of "ABCDE" and "ACE".
Solution
Build the 2D DP table where = LCS of first chars of s1 and first chars of s2:
- A matches A → dp[1][1] = 1
- C matches C → dp[3][2] = 2
- E matches E → dp[5][3] = 3 Answer: 3 (the LCS is "ACE")
Problem 4: Given the array [10, 9, 2, 5, 3, 7, 101, 18], find the length of the Longest Increasing Subsequence.
Solution
Using the patience sorting / binary search approach, maintain tails:
- 10 → tails=[10]
- 9 → replace 10 → tails=[9]
- 2 → replace 9 → tails=[2]
- 5 → append → tails=[2,5]
- 3 → replace 5 → tails=[2,3]
- 7 → append → tails=[2,3,7]
- 101 → append → tails=[2,3,7,101]
- 18 → replace 101 → tails=[2,3,7,18] Answer: 4 (e.g., [2, 3, 7, 101] or [2, 3, 7, 18])
Problem 5: Compute the edit distance between "kitten" and "sitting".
Solution
Build the DP table:
- k→s (replace), i=i, t=t, t→t, e→i (replace), n→n, +g (insert) Step by step: kitten → sitten (replace k with s) → sittin (replace e with i) → sitting (insert g) Answer: 3 operations
Quick Quiz
1. What two properties must a problem have to be solvable with dynamic programming?
- a) Greedy choice property and optimal substructure
- b) Optimal substructure and overlapping subproblems
- c) Divide and conquer with no overlapping subproblems
- d) Polynomial time and constant space
Answer
b) Optimal substructure and overlapping subproblems — Optimal substructure means the optimal solution contains optimal solutions to subproblems. Overlapping subproblems means the same subproblems are solved multiple times, making caching beneficial.
2. What is the key difference between top-down (memoization) and bottom-up (tabulation) DP?
- a) Top-down is always faster
- b) Top-down uses recursion with caching; bottom-up fills a table iteratively
- c) Bottom-up cannot be space-optimized
- d) Top-down solves all subproblems; bottom-up only solves needed ones
Answer
b) Top-down uses recursion with caching; bottom-up fills a table iteratively — Top-down starts from the main problem and recurses downward. Bottom-up builds from the smallest subproblems upward. Top-down may skip unneeded subproblems but risks stack overflow.
3. What is the time complexity of the 0/1 Knapsack problem with items and capacity ?
- a)
- b)
- c)
- d)
Answer
b) — The DP table has entries, each computed in . Note this is pseudo-polynomial: polynomial in the value of , not in the number of bits to represent it.
4. In the space-optimized 0/1 Knapsack, why must you iterate the capacity in reverse?
- a) To sort the items by weight
- b) To prevent using the same item more than once in the same row
- c) To improve cache performance
- d) To reduce the number of iterations
Answer
b) To prevent using the same item more than once in the same row — Forward iteration would use the already-updated values from the current row, effectively allowing item reuse (which is the unbounded knapsack). Reverse iteration ensures you only reference values from the previous row.
5. Which DP pattern best describes the Edit Distance problem?
- a) 1D linear sequence
- b) 2D two-sequence comparison
- c) Interval DP
- d) Bitmask DP
Answer
b) 2D two-sequence comparison — Edit distance compares two strings character by character, with state dp[i][j] representing the edit distance between the first characters of one string and the first characters of the other.
Lessons: next — DP Foundations · module — Dynamic Programming · course — DSA: Zero to Mastery. Previous module: Module 5 · Paradigms. Next module: String Algorithms.