Dynamic Programming
How to identify DP problems, define state, write transitions, and master the core patterns — fibonacci, knapsack, LCS, and grid paths
Dynamic Programming
Dynamic programming is an optimization technique for problems with overlapping subproblems and optimal substructure. If you can solve a problem by combining solutions to smaller versions of the same problem, and those smaller problems repeat, DP applies.
The hard part is not the code — it is recognising the problem and defining the state.
How to identify DP problems
Ask these questions:
- Can the problem be broken into smaller subproblems of the same type?
- Do subproblems overlap (same subproblem solved multiple times)?
- Does the problem ask for an optimal value (min, max, count)?
If all three are yes, it is likely DP. If only 1 and 2 are yes (no optimization), it might be divide-and-conquer instead.
Common signals in problem statements: "minimum cost", "maximum profit", "number of ways", "is it possible" (with constraints implying exponential brute force).
Top-down vs. bottom-up
Top-down (memoization)
Start from the original problem, recurse into subproblems, cache results.
function fib(n: number, memo = new Map<number, number>()): number {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n)!;
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result);
return result;
}Pros: natural to write if you can express the recursion, only computes needed subproblems. Cons: recursion stack overhead, harder to optimize space.
Bottom-up (tabulation)
Build a table from the smallest subproblems upward.
function fib(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];
}Pros: no recursion stack, easier to optimize space (rolling variables). Cons: computes all subproblems even if some are unnecessary.
Framework for solving DP problems
Step 1: Define state
What variables describe a subproblem? The state is the minimum set of parameters that uniquely identifies a subproblem.
dp[i]= answer for the firstielementsdp[i][j]= answer for subarray[i..j]or using firstiitems with capacityj
Step 2: Write the recurrence
How does the solution to a larger problem relate to smaller ones?
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (house robber)
Step 3: Identify base cases
What are the smallest subproblems you can solve directly?
dp[0] = 0, dp[1] = nums[0]
Step 4: Determine build order
Bottom-up: fill from base cases toward the answer. Top-down: recursion handles this automatically.
Step 5: Optimize space (optional)
If dp[i] only depends on dp[i-1] and dp[i-2], you only need two variables.
Pattern 1: 1D DP
Climbing stairs
dp[i] = number of ways to reach step i.
function climbStairs(n: number): number {
let prev2 = 1, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}House robber
Cannot rob adjacent houses. dp[i] = max money from first i houses.
function rob(nums: number[]): number {
let prev2 = 0, prev1 = 0;
for (const num of nums) {
const curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Coin change (minimum coins)
dp[amount] = minimum coins needed to make amount.
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] !== Infinity) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}Pattern 2: 2D DP
Unique paths (grid)
dp[i][j] = number of paths from (0,0) to (i,j).
function uniquePaths(m: number, n: number): number {
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}Longest Common Subsequence
dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1].
function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length, 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];
}Edit distance
dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1].
function minDistance(word1: string, word2: string): number {
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
);
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], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[m][n];
}Pattern 3: Knapsack
0/1 Knapsack
Each item used at most once. dp[i][w] = max value using first i items with capacity w.
function knapsack(weights: number[], values: number[], capacity: number): number {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]; // skip item i
if (weights[i - 1] <= w) {
dp[i][w] = Math.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):
function knapsack(weights: number[], values: number[], capacity: number): number {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}Unbounded knapsack (coin change variant)
Each item can be used unlimited times. Inner loop goes forward.
function coinChangeWays(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}Space optimization
If dp[i] depends only on dp[i-1] (the previous row), keep only two rows or use a single row updated in the right direction:
- 0/1 knapsack: iterate capacity in reverse (right to left) so you don't use updated values from the same row.
- Unbounded knapsack: iterate capacity forward (left to right) because reusing the same item is allowed.
- 1D problems: often reduce to two or three variables.
Common mistakes
- Wrong state definition — the state does not uniquely identify the subproblem. Adding a dimension usually fixes it.
- Wrong base cases — off-by-one errors. Think: "what is the answer for the empty/trivial case?"
- Wrong build order — computing
dp[i]before its dependencies are ready. - Forgetting to handle impossible states — use
Infinityor-Infinityas sentinels, check before using. - Not considering that the answer might not be
dp[n]— sometimes you needmax(dp[0..n])(e.g., longest increasing subsequence).