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 values
Example: 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 approach
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 recursion
1. 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.