Dynamic Programming (DP) Patterns
1. 0/1 Knapsack Problem (Space Optimization)
| Approach | Space | Technique | Trade-off |
|---|---|---|---|
| 2D DP Table | O(n*W) |
dp[i][w] = max value with first i items, capacity w | Straightforward, can reconstruct solution |
| 1D DP Array | O(W) |
Process items one by one, update in reverse | Space optimized, harder to reconstruct items |
| Reverse Iteration | Required for 1D | Prevents using updated values from same iteration | Critical for correctness |
| State Transition | Take or skip item | dp[w] = max(dp[w], dp[w-weight] + value) |
Classic 0/1 knapsack formula |
Example: 0/1 Knapsack 2D DP
function knapsack2D(weights, values, capacity) {
const n = weights.length;
// dp[i][w] = max value using first i items with capacity w
const dp = Array(n + 1).fill(null)
.map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
// Option 1: Don't take item i-1
dp[i][w] = dp[i - 1][w];
// Option 2: Take item i-1 (if fits)
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];
}
// weights=[1,3,4,5], values=[1,4,5,7], capacity=7
// -> 9 (take items 1 and 3: values 4+5)
// Time: O(n*W), Space: O(n*W)Example: 0/1 Knapsack 1D optimized
function knapsack1D(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// MUST iterate backwards!
// Prevents using updated values from current iteration
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(
dp[w], // Don't take item i
dp[w - weights[i]] + values[i] // Take item i
);
}
}
return dp[capacity];
}
// Same result: 9
// Time: O(n*W), Space: O(W)
// Key: Reverse iteration preserves previous row valuesExample: Partition equal subset sum (0/1 knapsack variant)
function canPartition(nums) {
const sum = nums.reduce((a, b) => a + b, 0);
// If odd sum, can't partition equally
if (sum % 2 !== 0) return false;
const target = sum / 2;
const dp = Array(target + 1).fill(false);
dp[0] = true; // Base case: sum 0 is always achievable
for (const num of nums) {
// Iterate backwards (0/1 knapsack pattern)
for (let j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
// [1,5,11,5] -> true (partition: [1,5,5] and [11])
// [1,2,3,5] -> false
// Time: O(n*sum), Space: O(sum)2. Unbounded Knapsack (Bottom-Up DP)
| Difference from 0/1 | Implementation | Reason | Application |
|---|---|---|---|
| Unlimited Items | Can use same item multiple times | Forward iteration in inner loop | Coin change, rod cutting |
| Forward Iteration | Use updated values in same iteration | Allows reusing same item | Different from 0/1's reverse iteration |
| State Transition | dp[w] = max(dp[w], dp[w-weight] + value) |
Can revisit dp[w-weight] after update | Enables unlimited use |
| Space Optimization | 1D array sufficient | Only need current state | O(W) space |
Example: Unbounded knapsack
function unboundedKnapsack(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// Forward iteration (key difference!)
for (let w = weights[i]; w <= capacity; w++) {
dp[w] = Math.max(
dp[w],
dp[w - weights[i]] + values[i]
);
}
}
return dp[capacity];
}
// weights=[1,3,4], values=[15,20,25], capacity=4
// Can use item multiple times
// Best: take item 0 four times (15*4=60) or
// take item 2 once (25)
// Time: O(n*W), Space: O(W)Example: Coin change (ways to make amount)
function change(amount, coins) {
const dp = Array(amount + 1).fill(0);
dp[0] = 1; // One way to make 0: use no coins
for (const coin of coins) {
// Forward iteration for unbounded
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// amount=5, coins=[1,2,5]
// Ways: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]
// -> 4 ways
// Time: O(n*amount), Space: O(amount)Example: Rod cutting problem
function rodCutting(prices, length) {
// prices[i] = price of rod of length i+1
const dp = Array(length + 1).fill(0);
for (let len = 1; len <= length; len++) {
for (let cut = 1; cut <= len; cut++) {
// Try cutting piece of length 'cut'
dp[len] = Math.max(
dp[len],
prices[cut - 1] + dp[len - cut]
);
}
}
return dp[length];
}
// prices=[1,5,8,9,10,17,17,20], length=8
// Best: cut into 2+6 for price 5+17=22
// Time: O(n²), Space: O(n)3. Longest Common Subsequence (LCS Algorithm)
| Concept | State Definition | Transition | Complexity |
|---|---|---|---|
| Subsequence | Characters in order, not necessarily consecutive | Different from substring (must be consecutive) | More flexible matching |
| DP Table | dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1] | 2D table, bottom-up or top-down | O(m*n) time and space |
| Match Case | If s1[i-1] === s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 | Extend previous LCS by 1 | Characters match |
| Mismatch Case | Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) | Take best by skipping one character | Try both options |
Example: Longest common subsequence
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
// dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
const dp = Array(m + 1).fill(null)
.map(() => 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]) {
// Characters match: extend LCS
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// Characters don't match: take max
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// "abcde", "ace" -> 3 (LCS = "ace")
// "abc", "abc" -> 3 (LCS = "abc")
// "abc", "def" -> 0 (no common subsequence)
// Time: O(m*n), Space: O(m*n)Example: LCS with path reconstruction
function lcsWithPath(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill(null)
.map(() => Array(n + 1).fill(0));
// Build DP table
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]);
}
}
}
// Reconstruct LCS
let i = m, j = n;
const lcs = [];
while (i > 0 && j > 0) {
if (text1[i - 1] === text2[j - 1]) {
lcs.unshift(text1[i - 1]);
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return {
length: dp[m][n],
sequence: lcs.join('')
};
}
// "ABCDGH", "AEDFHR"
// -> {length: 3, sequence: "ADH"}Example: Space-optimized LCS O(min(m,n))
function lcsSpaceOptimized(text1, text2) {
// Ensure text1 is shorter for space efficiency
if (text1.length > text2.length) {
[text1, text2] = [text2, text1];
}
const m = text1.length;
const n = text2.length;
let prev = Array(m + 1).fill(0);
let curr = Array(m + 1).fill(0);
for (let j = 1; j <= n; j++) {
for (let i = 1; i <= m; i++) {
if (text1[i - 1] === text2[j - 1]) {
curr[i] = prev[i - 1] + 1;
} else {
curr[i] = Math.max(curr[i - 1], prev[i]);
}
}
[prev, curr] = [curr, prev];
}
return prev[m];
}
// Space: O(min(m,n)) instead of O(m*n)
// Can't reconstruct path with this approach4. Longest Increasing Subsequence (LIS O(n log n))
| Approach | Method | Time | Space |
|---|---|---|---|
| DP O(n²) | For each i, check all j < i | O(n²) |
O(n) |
| Binary Search | Maintain tails array, binary search for position | O(n log n) |
O(n) |
| DP State | dp[i] = length of LIS ending at index i | Must check all previous elements | Simple to understand |
| Tails Array | tails[i] = smallest tail of LIS of length i+1 | Optimal for finding length only | Complex but efficient |
Example: LIS with O(n²) DP
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
// [10,9,2,5,3,7,101,18]
// dp = [1,1,1,2,2,3,4,4]
// LIS: [2,3,7,101] or [2,5,7,101], length = 4
// Time: O(n²), Space: O(n)Example: LIS with binary search O(n log n)
function lengthOfLISOptimal(nums) {
const tails = [];
for (const num of nums) {
// Binary search for position
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
// Replace or append
if (left === tails.length) {
tails.push(num);
} else {
tails[left] = num;
}
}
return tails.length;
}
// tails[i] = smallest ending value of LIS of length i+1
// Time: O(n log n), Space: O(n)Example: LIS with reconstruction
function lisWithPath(nums) {
if (nums.length === 0) return [];
const dp = Array(nums.length).fill(1);
const prev = Array(nums.length).fill(-1);
let maxLen = 1;
let maxIndex = 0;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j; // Track predecessor
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
maxIndex = i;
}
}
// Reconstruct LIS
const lis = [];
let idx = maxIndex;
while (idx !== -1) {
lis.unshift(nums[idx]);
idx = prev[idx];
}
return lis;
}
// [10,9,2,5,3,7,101,18]
// -> [2,3,7,101] (one possible LIS)
Note: Key DP patterns: 0/1 Knapsack uses reverse iteration for 1D optimization, Unbounded Knapsack uses forward iteration to allow item reuse. LCS is fundamental for diff algorithms and bioinformatics. LIS has O(n²) DP solution and O(n log n) binary search optimization.
5. Coin Change Minimum Coins Problem
| Variant | State Definition | Transition | Base Case |
|---|---|---|---|
| Min Coins | dp[i] = min coins to make amount i | dp[i] = min(dp[i], dp[i-coin] + 1) | dp[0] = 0, others = Infinity |
| Count Ways | dp[i] = ways to make amount i | dp[i] += dp[i-coin] | dp[0] = 1, others = 0 |
| Unbounded Type | Can use same coin multiple times | Forward iteration | Classic unbounded knapsack |
| Impossible Case | If dp[amount] remains Infinity | Return -1 | No combination exists |
Example: Coin change minimum coins
function coinChange(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0; // 0 coins needed for amount 0
for (const coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// coins=[1,2,5], amount=11
// -> 3 (5+5+1)
// coins=[2], amount=3
// -> -1 (impossible)
// Time: O(n*amount), Space: O(amount)Example: Coin change with path
function coinChangeWithPath(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
const parent = Array(amount + 1).fill(-1);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
parent[i] = coin;
}
}
}
if (dp[amount] === Infinity) return null;
// Reconstruct path
const result = [];
let curr = amount;
while (curr > 0) {
result.push(parent[curr]);
curr -= parent[curr];
}
return result;
}
// coins=[1,2,5], amount=11
// -> [5,5,1]Example: Coin change II (count ways)
function change(amount, coins) {
const dp = Array(amount + 1).fill(0);
dp[0] = 1; // One way to make 0
// IMPORTANT: Iterate coins in outer loop
// to avoid counting permutations
for (const coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
// amount=5, coins=[1,2,5]
// Ways: [5], [2,2,1], [2,1,1,1], [1,1,1,1,1]
// -> 4 ways
// If we iterate amount in outer loop, we get permutations instead!
// Time: O(n*amount), Space: O(amount)6. Palindromic Substrings (Expand Around Centers)
| Approach | Method | Time | Advantage |
|---|---|---|---|
| DP 2D Table | dp[i][j] = is s[i..j] palindrome | O(n²) |
Can query any substring |
| Expand Centers | Try each position as center, expand outward | O(n²) |
Better space O(1), simpler code |
| Odd Length | Single character center | Expand while s[i-k] === s[i+k] | Center at index i |
| Even Length | Two character center | Expand while s[i] === s[i+1+k] | Center between i and i+1 |
Example: Count palindromic substrings
function countSubstrings(s) {
let count = 0;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length &&
s[left] === s[right]) {
count++;
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
// Odd length palindromes (center at i)
expandAroundCenter(i, i);
// Even length palindromes (center between i and i+1)
expandAroundCenter(i, i + 1);
}
return count;
}
// "abc" -> 3 ("a", "b", "c")
// "aaa" -> 6 ("a", "a", "a", "aa", "aa", "aaa")
// Time: O(n²), Space: O(1)Example: Longest palindromic substring
function longestPalindrome(s) {
let start = 0;
let maxLen = 0;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length &&
s[left] === s[right]) {
const len = right - left + 1;
if (len > maxLen) {
start = left;
maxLen = len;
}
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // Odd
expandAroundCenter(i, i + 1); // Even
}
return s.substring(start, start + maxLen);
}
// "babad" -> "bab" or "aba"
// "cbbd" -> "bb"
// Time: O(n²), Space: O(1)Example: Palindromic substrings DP approach
function countSubstringsDP(s) {
const n = s.length;
const dp = Array(n).fill(null).map(() => Array(n).fill(false));
let count = 0;
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
dp[i][i] = true;
count++;
}
// Check substrings of length 2
for (let i = 0; i < n - 1; i++) {
if (s[i] === s[i + 1]) {
dp[i][i + 1] = true;
count++;
}
}
// Check substrings of length 3+
for (let len = 3; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
count++;
}
}
}
return count;
}
// Same results as expand approach
// Time: O(n²), Space: O(n²)7. Edit Distance (Levenshtein Distance Algorithm)
| Operation | Description | State Transition | Example |
|---|---|---|---|
| Insert | Add character to word1 | dp[i][j] = dp[i][j-1] + 1 | "abc" → "abdc" (insert 'd') |
| Delete | Remove character from word1 | dp[i][j] = dp[i-1][j] + 1 | "abc" → "ac" (delete 'b') |
| Replace | Change character in word1 | dp[i][j] = dp[i-1][j-1] + 1 | "abc" → "adc" (replace 'b' with 'd') |
| Match | Characters already equal | dp[i][j] = dp[i-1][j-1] | No operation needed |
Example: Edit distance (Levenshtein distance)
function minDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
// dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
const dp = Array(m + 1).fill(null)
.map(() => Array(n + 1).fill(0));
// Base cases: convert empty string
for (let i = 0; i <= m; i++) dp[i][0] = i; // Delete all
for (let j = 0; j <= n; j++) dp[0][j] = j; // Insert all
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
// Characters match, no operation needed
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete
dp[i][j - 1] + 1, // Insert
dp[i - 1][j - 1] + 1 // Replace
);
}
}
}
return dp[m][n];
}
// "horse", "ros" -> 3
// horse -> rorse (replace 'h' with 'r')
// rorse -> rose (remove 'r')
// rose -> ros (remove 'e')
// Time: O(m*n), Space: O(m*n)Example: Space-optimized edit distance
function minDistanceOptimized(word1, word2) {
const m = word1.length;
const n = word2.length;
let prev = Array(n + 1).fill(0);
let curr = Array(n + 1).fill(0);
// Initialize base case
for (let j = 0; j <= n; j++) prev[j] = j;
for (let i = 1; i <= m; i++) {
curr[0] = i; // Base case for current row
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
curr[j] = prev[j - 1];
} else {
curr[j] = Math.min(
prev[j] + 1, // Delete
curr[j - 1] + 1, // Insert
prev[j - 1] + 1 // Replace
);
}
}
[prev, curr] = [curr, prev];
}
return prev[n];
}
// Same result, Space: O(n) instead of O(m*n)Example: One edit distance
function isOneEditDistance(s, t) {
const m = s.length;
const n = t.length;
// Length difference must be 0 or 1
if (Math.abs(m - n) > 1) return false;
if (s === t) return false; // Must be exactly one edit
let i = 0;
// Find first difference
while (i < Math.min(m, n) && s[i] === t[i]) {
i++;
}
if (m === n) {
// Replace: rest must match
return s.slice(i + 1) === t.slice(i + 1);
} else if (m < n) {
// Insert into s: skip one char in t
return s.slice(i) === t.slice(i + 1);
} else {
// Delete from s: skip one char in s
return s.slice(i + 1) === t.slice(i);
}
}
// "ab", "acb" -> true (insert 'c')
// "cab", "ad" -> false (2 edits)
// Time: O(n), Space: O(1)8. Maximum Subarray Sum (Kadane's Algorithm)
| Concept | Description | Formula | Complexity |
|---|---|---|---|
| Core Idea | At each position, extend or start new subarray | Either continue or restart | Greedy choice at each step |
| State | maxEndingHere = max sum ending at current position | max(nums[i], maxEndingHere + nums[i]) |
Local maximum |
| Global Max | Track best result seen so far | max(maxSoFar, maxEndingHere) |
Answer |
| Performance | Single pass through array | O(n) time, O(1) space |
Optimal solution |
Example: Kadane's algorithm
function maxSubArray(nums) {
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
for (let i = 1; i < nums.length; i++) {
// Either extend current subarray or start new
maxEndingHere = Math.max(
nums[i],
maxEndingHere + nums[i]
);
// Update global maximum
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
// [-2,1,-3,4,-1,2,1,-5,4]
// maxEndingHere: [-2,1,-2,4,3,5,6,1,5]
// -> 6 (subarray [4,-1,2,1])
// Time: O(n), Space: O(1)Example: Kadane with indices
function maxSubArrayWithIndices(nums) {
let maxSoFar = nums[0];
let maxEndingHere = nums[0];
let start = 0, end = 0, tempStart = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] > maxEndingHere + nums[i]) {
maxEndingHere = nums[i];
tempStart = i; // New subarray starts
} else {
maxEndingHere = maxEndingHere + nums[i];
}
if (maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
start = tempStart;
end = i;
}
}
return {
sum: maxSoFar,
subarray: nums.slice(start, end + 1)
};
}
// [-2,1,-3,4,-1,2,1,-5,4]
// -> {sum: 6, subarray: [4,-1,2,1]}Example: Circular array maximum subarray
function maxSubarraySumCircular(nums) {
function kadane(arr) {
let maxSoFar = arr[0];
let maxEndingHere = arr[0];
for (let i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
// Case 1: Maximum subarray is in the middle (normal Kadane)
const maxNormal = kadane(nums);
// Case 2: Maximum subarray wraps around
// Find minimum subarray, subtract from total
const total = nums.reduce((a, b) => a + b, 0);
const inverted = nums.map(x => -x);
const maxInverted = kadane(inverted);
const maxWrap = total + maxInverted; // total - minSubarray
// Edge case: all negative numbers
if (maxWrap === 0) return maxNormal;
return Math.max(maxNormal, maxWrap);
}
// [5,-3,5] -> 10 (wrap: 5+5)
// [1,-2,3,-2] -> 3 (normal)
// Time: O(n), Space: O(n) for inverted array
Note: Coin Change is fundamental unbounded knapsack. Palindromes use expand-from-center for O(1) space or DP for substring queries. Edit Distance is essential for spell checkers and DNA sequencing. Kadane's Algorithm is the optimal O(n) solution for maximum subarray, can be adapted for 2D, circular arrays, and product variants.
9. House Robber Problem (DP State Transitions)
| Variant | Constraint | State | Transition |
|---|---|---|---|
| House Robber I | Linear array, can't rob adjacent | dp[i] = max money up to house i | max(dp[i-1], dp[i-2] + nums[i]) |
| House Robber II | Circular array, first and last adjacent | Two cases: rob first or rob last | max(rob(0..n-2), rob(1..n-1)) |
| House Robber III | Binary tree, can't rob parent and child | {rob: maxIfRob, skip: maxIfSkip} | Tree DP with two states per node |
| Space Optimization | Only need last 2 values | Two variables instead of array | O(1) space |
Example: House robber I
function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = nums[0];
let prev1 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const curr = Math.max(
prev1, // Skip current house
prev2 + nums[i] // Rob current house
);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// [1,2,3,1] -> 4 (rob houses 0 and 2: 1+3=4)
// [2,7,9,3,1] -> 12 (rob houses 0,2,4: 2+9+1=12)
// Time: O(n), Space: O(1)Example: House robber II (circular)
function robCircular(nums) {
if (nums.length === 1) return nums[0];
if (nums.length === 2) return Math.max(nums[0], nums[1]);
function robLinear(start, end) {
let prev2 = 0, prev1 = 0;
for (let i = start; i <= end; i++) {
const curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Case 1: Rob houses 0 to n-2 (exclude last)
// Case 2: Rob houses 1 to n-1 (exclude first)
return Math.max(
robLinear(0, nums.length - 2),
robLinear(1, nums.length - 1)
);
}
// [2,3,2] -> 3 (can't rob both 0 and 2)
// [1,2,3,1] -> 4 (rob 1 and 3)
// Time: O(n), Space: O(1)Example: House robber III (binary tree)
function robTree(root) {
// Returns {rob: maxIfRobRoot, skip: maxIfSkipRoot}
function dfs(node) {
if (!node) return { rob: 0, skip: 0 };
const left = dfs(node.left);
const right = dfs(node.right);
// If we rob this node, can't rob children
const rob = node.val + left.skip + right.skip;
// If we skip this node, take max from children
const skip = Math.max(left.rob, left.skip) +
Math.max(right.rob, right.skip);
return { rob, skip };
}
const result = dfs(root);
return Math.max(result.rob, result.skip);
}
// 3
// / \
// 2 3
// \ \
// 3 1
// -> 7 (rob 3, 3, 1)
// Time: O(n), Space: O(h) for recursion1. 0/1 Knapsack Problem (Space Optimization)
| Pattern | State | Recurrence | Use Case |
|---|---|---|---|
| Tree DP | Compute value at node using children | Post-order traversal (children first) | Diameter, path sum, subtree properties |
| Multiple States | Track different scenarios per node | Return object/array with all states | Include/exclude node, different paths |
| Parent Info | Pass info down from parent | Pre-order or two-pass approach | Distance from root, parent values |
| Rerooting | Answer for each node as root | Two DFS: compute subtree, then reroot | Sum of distances to all nodes |
Example: Binary tree diameter
function diameterOfBinaryTree(root) {
let diameter = 0;
function height(node) {
if (!node) return 0;
const leftHeight = height(node.left);
const rightHeight = height(node.right);
// Diameter through this node
diameter = Math.max(
diameter,
leftHeight + rightHeight
);
// Return height for parent
return 1 + Math.max(leftHeight, rightHeight);
}
height(root);
return diameter;
}
// 1
// / \
// 2 3
// / \
// 4 5
// -> 3 (path 4-2-1-3 or 5-2-1-3)
// Time: O(n), Space: O(h)Example: Binary tree maximum path sum
function maxPathSum(root) {
let maxSum = -Infinity;
function maxGain(node) {
if (!node) return 0;
// Get max gain from children (ignore negative)
const leftGain = Math.max(maxGain(node.left), 0);
const rightGain = Math.max(maxGain(node.right), 0);
// Path through current node
const pathSum = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, pathSum);
// Return max gain through this node
// (can only use one child)
return node.val + Math.max(leftGain, rightGain);
}
maxGain(root);
return maxSum;
}
// -10
// / \
// 9 20
// / \
// 15 7
// -> 42 (path 15-20-7)
// Time: O(n), Space: O(h)Example: Count good nodes in tree
function goodNodes(root) {
let count = 0;
function dfs(node, maxSoFar) {
if (!node) return;
// Good node: value >= max on path from root
if (node.val >= maxSoFar) {
count++;
maxSoFar = node.val;
}
dfs(node.left, maxSoFar);
dfs(node.right, maxSoFar);
}
dfs(root, -Infinity);
return count;
}
// 3
// / \
// 1 4
// / / \
// 3 1 5
// -> 4 (nodes 3,3,4,5 are good)
// Time: O(n), Space: O(h)1. 0/1 Knapsack Problem (Space Optimization)
| Concept | Representation | Operations | Use Case |
|---|---|---|---|
| State Compression | Use bits to represent subset | Each bit = element included/excluded | Track visited states compactly |
| Check Bit | (mask >> i) & 1 |
Test if i-th element included | Query state |
| Set Bit | mask | (1 << i) |
Include i-th element | Transition to new state |
| Clear Bit | mask & ~(1 << i) |
Exclude i-th element | Remove from state |
Example: Traveling salesman problem (TSP)
function tsp(dist) {
const n = dist.length;
const VISITED_ALL = (1 << n) - 1;
// dp[mask][i] = min cost to visit cities in mask, ending at i
const dp = Array(1 << n).fill(null)
.map(() => Array(n).fill(Infinity));
dp[1][0] = 0; // Start at city 0
for (let mask = 0; mask <= VISITED_ALL; mask++) {
for (let last = 0; last < n; last++) {
if (!(mask & (1 << last))) continue;
if (dp[mask][last] === Infinity) continue;
for (let next = 0; next < n; next++) {
if (mask & (1 << next)) continue;
const newMask = mask | (1 << next);
dp[newMask][next] = Math.min(
dp[newMask][next],
dp[mask][last] + dist[last][next]
);
}
}
}
// Find min cost ending at any city
let result = Infinity;
for (let i = 0; i < n; i++) {
result = Math.min(result,
dp[VISITED_ALL][i] + dist[i][0]);
}
return result;
}
// Time: O(2^n * n²), Space: O(2^n * n)Example: Minimum cost to connect all points (Steiner tree)
function assignTasks(servers, tasks) {
const n = servers.length;
const m = tasks.length;
// dp[mask] = min cost to assign tasks in mask
const dp = Array(1 << m).fill(Infinity);
dp[0] = 0;
for (let mask = 0; mask < (1 << m); mask++) {
if (dp[mask] === Infinity) continue;
// Count assigned tasks
const assigned = countBits(mask);
if (assigned >= n) continue;
for (let task = 0; task < m; task++) {
if (mask & (1 << task)) continue;
const newMask = mask | (1 << task);
const cost = servers[assigned] * tasks[task];
dp[newMask] = Math.min(
dp[newMask],
dp[mask] + cost
);
}
}
return dp[(1 << m) - 1];
}
function countBits(n) {
let count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
// Time: O(2^m * m * n), Space: O(2^m)Example: Partition into k equal sum subsets
function canPartitionKSubsets(nums, k) {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % k !== 0) return false;
const target = sum / k;
nums.sort((a, b) => b - a);
if (nums[0] > target) return false;
const n = nums.length;
const dp = Array(1 << n).fill(-1);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask] === -1) continue;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) continue;
const newSum = dp[mask] + nums[i];
if (newSum > target) continue;
const newMask = mask | (1 << i);
if (dp[newMask] !== -1) continue;
dp[newMask] = newSum % target;
}
}
return dp[(1 << n) - 1] === 0;
}
// [4,3,2,3,5,2,1], k=4 -> true
// Can partition into [5], [1,4], [2,3], [2,3]
// Time: O(2^n * n), Space: O(2^n)1. 0/1 Knapsack Problem (Space Optimization)
| Pattern | State | Iteration Order | Example |
|---|---|---|---|
| Interval DP | dp[i][j] = answer for subarray/substring [i..j] | Increasing interval length | Optimal way to merge/split interval |
| Length Loop | Outer loop: interval length from 1 to n | Build small intervals first | Ensures subproblems solved |
| Split Point | Try all ways to split [i..j] | dp[i][j] = min/max over all k in [i..j] | Matrix chain, burst balloons |
| Complexity | Usually O(n³) | n² states, O(n) transition | Can optimize with monotonic queue |
Example: Matrix chain multiplication
function matrixChainOrder(dims) {
// dims[i] = dimensions of matrix i
// Matrix i has dimensions dims[i-1] x dims[i]
const n = dims.length - 1;
// dp[i][j] = min multiplications for matrices i to j
const dp = Array(n).fill(null)
.map(() => Array(n).fill(0));
// len = chain length
for (let len = 2; len <= n; len++) {
for (let i = 0; i < n - len + 1; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
// Try splitting at k
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k + 1][j] +
dims[i] * dims[k + 1] * dims[j + 1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
// dims = [10, 20, 30, 40, 30]
// Matrices: A(10x20), B(20x30), C(30x40), D(40x30)
// Optimal: ((A*B)*C)*D = 30,000 multiplications
// Time: O(n³), Space: O(n²)Example: Burst balloons
function maxCoins(nums) {
// Add virtual balloons with value 1
const arr = [1, ...nums, 1];
const n = arr.length;
// dp[i][j] = max coins from bursting balloons (i+1..j-1)
const dp = Array(n).fill(null)
.map(() => Array(n).fill(0));
for (let len = 2; len < n; len++) {
for (let left = 0; left < n - len; left++) {
const right = left + len;
// Try bursting k last in range (left+1..right-1)
for (let k = left + 1; k < right; k++) {
const coins = arr[left] * arr[k] * arr[right] +
dp[left][k] + dp[k][right];
dp[left][right] = Math.max(
dp[left][right],
coins
);
}
}
}
return dp[0][n - 1];
}
// [3,1,5,8] -> 167
// Burst order: 1,5,3,8
// 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
// Time: O(n³), Space: O(n²)Example: Palindrome partitioning II
function minCut(s) {
const n = s.length;
// isPalin[i][j] = is s[i..j] palindrome
const isPalin = Array(n).fill(null)
.map(() => Array(n).fill(false));
// Build palindrome table
for (let len = 1; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (len === 1) {
isPalin[i][j] = true;
} else if (len === 2) {
isPalin[i][j] = s[i] === s[j];
} else {
isPalin[i][j] = s[i] === s[j] &&
isPalin[i + 1][j - 1];
}
}
}
// dp[i] = min cuts for s[0..i]
const dp = Array(n).fill(Infinity);
for (let i = 0; i < n; i++) {
if (isPalin[0][i]) {
dp[i] = 0;
} else {
for (let j = 0; j < i; j++) {
if (isPalin[j + 1][i]) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
}
return dp[n - 1];
}
// "aab" -> 1 (cut: "aa|b")
// "a" -> 0 (already palindrome)
// Time: O(n²), Space: O(n²)
Warning: Dynamic programming requires identifying optimal substructure and overlapping subproblems. Space optimization (2D→1D) is common but may prevent path reconstruction. For bitmask DP, limit to n≤20 due to exponential states. Interval DP typically needs O(n³) time - ensure n is manageable. Always verify base cases and state transitions carefully.
Summary: Dynamic Programming is solving complex problems by breaking them into overlapping subproblems. Key techniques: Knapsack (0/1 and Unbounded) for subset selection, LCS/LIS for sequence problems, Edit Distance for string transformations, Kadane for optimal subarrays, Tree DP for hierarchical structures, Bitmask DP for subset enumeration, and Interval DP for range optimization. Master state definition, transition formulas, and space optimization techniques.