DP Puzzles

You cannot rob two adjacent houses. For each house, decide: rob it (add its value to the profit two positions back) or skip it (keep the profit from the previous position).

The recurrence is: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Only the two previous DP values are needed at any point, so use two variables for O(1) space instead of a full array.

This runs in O(n) time and O(1) space.

function rob(nums) {
  let prev2 = 0, prev1 = 0;
  for (let n of nums) {
    let curr = Math.max(prev1, prev2 + n);
    prev2 = prev1; prev1 = curr;
  }
  return prev1;
}

Two-variable rolling DP: prev2 holds dp[i-2] and prev1 holds dp[i-1]; update both each iteration to maintain the recurrence without an array.

House Robber II (circular array) splits into two subproblems: rob houses 0..(n-2) and rob houses 1..(n-1), then take the maximum of both results.

Given coin denominations and a target amount, find the minimum number of coins needed. Coins can be reused any number of times (unbounded Knapsack variant).

Define dp[i] as the minimum coins to make amount i. Initialize all cells to Infinity except dp[0] = 0 (zero coins for amount zero).

For each coin c, update all amounts from c to target: dp[i] = min(dp[i], dp[i-c] + 1). Forward traversal allows the same coin to be reused.

Time complexity is O(amount * coins) and space is O(amount).

function coinChange(coins, amount) {
  let dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let c of coins)
    for (let i = c; i <= amount; i++)
      dp[i] = Math.min(dp[i], dp[i - c] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Forward traversal for unbounded: Iterating i from low to high lets the same coin be counted multiple times — reverse it to get 0/1 Knapsack behavior.

Return -1 if dp[amount] remains Infinity — it means the target amount cannot be formed with any combination of the given coins.

A palindrome reads the same forwards and backwards. The expand-from-center technique checks palindromes efficiently without scanning all substrings.

For each character, expand outward from that character (odd-length center) and the gap to its right (even-length center) as long as characters match.

Track the start index and maximum length found; update when a longer palindrome is discovered during expansion.

This runs in O(n) time for each center and O(n) centers: overall O(n²) time with O(1) space.

function longestPalindrome(s) {
  let start = 0, maxLen = 1;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
    if (r - l - 1 > maxLen) { start = l + 1; maxLen = r - l - 1; }
  }
  for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }
  return s.substring(start, start + maxLen);
}

Two center types: Call expand for both (i, i) (odd-length) and (i, i+1) (even-length) at each position to cover all possible palindromes.

Manacher's algorithm solves this in O(n) using previously computed results but is significantly harder to implement — the expand approach is preferred in interview settings.

Kadane's Algorithm finds the subarray with the maximum sum in O(n) by making a greedy decision at each element.

For each element, decide whether to extend the existing subarray or start a new one: cur = max(num, cur + num). A negative running sum means starting fresh is always better.

Track the global maximum alongside the current running sum — update it whenever cur exceeds it.

This runs in O(n) time and O(1) space, compared to O(n²) or O(n³) for brute force approaches.

function maxSubArray(nums) {
  let max = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    max = Math.max(max, cur);
  }
  return max;
}

Greedy at each step: Math.max(num, cur + num) embodies the entire algorithm — if the current sum is negative, adding the current element still results in a suboptimal start, so restart.

To also return the indices of the maximum subarray, track when cur resets (new start candidate) and when max is updated (record end index and the candidate start).

Moving only right or down in an m x n grid, the number of unique paths to any cell equals the paths from above plus the paths from the left.

The first row and column each have exactly one path (all-right or all-down), forming the base cases. For every other cell: dp[i][j] = dp[i-1][j] + dp[i][j-1].

A 1D DP array of length n can replace the 2D array: update in-place as you scan each row, since only the current and previous row values are ever needed.

This runs in O(m x n) time and can be reduced to O(n) space.

function uniquePaths(m, n) {
  let dp = Array.from({length: m}, () => 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];
}

Initialize first row and column to 1: There is exactly one path to any cell in the first row (only move right) or first column (only move down) — these are the DP base cases.

The combinatorial closed form C(m+n-2, m-1) computes the same answer directly in O(m+n) time, useful when m and n are very large.

Word Break asks whether a string can be segmented into a space-separated sequence of dictionary words. Each portion must be a valid word in the given dictionary.

Use 1D DP: dp[i] is true if s[0..i-1] can be segmented. For each index i, check all split points j where dp[j] is true and s[j..i-1] is in the dictionary Set.

Using a Set for the dictionary gives O(1) word lookup, making the overall time O(n²) where n is the string length.

Space complexity is O(n) for the DP array plus O(dict size) for the Set.

function wordBreak(s, dict) {
  let set = new Set(dict), dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && set.has(s.substring(j, i))) { dp[i] = true; break; }
  return dp[s.length];
}

Early break on match: Once dp[i] is set to true, exit the inner loop immediately — additional j values cannot change the result and skipping them saves time.

Word Break II (returning all segmentations) stores all valid split points instead of a boolean and reconstructs paths through backtracking or memoized DFS.

A digit string encodes letters: '1' = 'A', '2' = 'B', ..., '26' = 'Z'. Count all distinct ways to decode the entire string.

Use DP where dp[i] is the count of ways to decode the first i digits. At each position check: if the single digit s[i-1] is valid (1-9), add dp[i-1]; if the two-digit number s[i-2..i-1] is 10-26, add dp[i-2].

Special case: leading zeros are invalid; '0' alone has no mapping and makes dp[i] = 0 if not part of 10 or 20.

This runs in O(n) time and O(n) space.

function numDecodings(s) {
  if (s[0] === '0') return 0;
  let n = s.length, dp = Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    if (s[i-1] !== '0') dp[i] += dp[i-1];
    let two = parseInt(s.substring(i-2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i-2];
  }
  return dp[n];
}

Zero handling: A '0' cannot be decoded alone (no letter maps to 0); it must be part of '10' or '20'. Any other two-digit starting with 0 (like '06') is invalid.

Space can be reduced to O(1) by using two variables prev1 and prev2 instead of the array since only the last two DP values are ever needed.

A subsequence preserves character order but not necessarily contiguity. The Longest Common Subsequence (LCS) is the longest sequence appearing in both strings as a subsequence.

Define dp[i][j] as the LCS length for the first i characters of string a and first j of string b. If characters match, extend the diagonal: dp[i-1][j-1] + 1. Otherwise, take the max of skipping one character from either string.

The final answer is in dp[m][n]. To reconstruct the actual subsequence, trace back through the table following diagonal moves for matches.

This runs in O(m × n) time and space, reducible to O(min(m, n)) with the rolling row technique.

function lcs(a, b) {
  let m = a.length, n = b.length;
  let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m][n];
}

Diagonal extension on match: When characters match, the LCS grows from the previous diagonal state — not from skipping one character, since that would not use both matched characters.

LCS is the foundation for diff algorithms (git diff), DNA sequence alignment, and the related edit distance problem which also counts insertions and deletions.

Given a grid of non-negative integers, find the path from top-left to bottom-right (moving only right or down) that minimizes the total sum.

Use DP where dp[i][j] holds the minimum sum to reach cell (i, j). For the first row and column, there is only one direction to come from. For other cells, take the minimum of top and left neighbors.

The DP can be done in-place on the original grid to save O(m × n) space.

This runs in O(m × n) time and O(1) extra space when modifying the grid in-place.

function minPathSum(grid) {
  let m = grid.length, n = grid[0].length;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      let top = i > 0 ? grid[i-1][j] : Infinity;
      let left = j > 0 ? grid[i][j-1] : Infinity;
      grid[i][j] += Math.min(top, left);
    }
  return grid[m-1][n-1];
}

In-place DP: Updating the grid itself eliminates the need for a separate dp array — the original grid cell values serve as the cumulative cost so far.

For paths with obstacles (cells set to -1 or blocked), add a check to treat blocked cells as Infinity so they are never selected as part of the minimum path.

Edit distance (Levenshtein distance) is the minimum number of insertions, deletions, or substitutions needed to transform one string into another.

Define dp[i][j] as the edit distance between the first i characters of word1 and first j characters of word2. If characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, take 1 + min of three operations (insert, delete, replace).

The base cases are: empty first string requires i insertions; empty second string requires j deletions.

This runs in O(m × n) time and O(m × n) space, reducible to O(min(m, n)) by using only two rows.

function minDistance(word1, word2) {
  let m = word1.length, n = word2.length;
  let dp = Array.from({length: m+1}, (_, i) => Array.from({length: n+1}, (_, j) => i || 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], dp[i][j-1], dp[i-1][j-1]);
    }
  return dp[m][n];
}

Three operations: Delete from word1 = dp[i-1][j]+1; insert into word1 = dp[i][j-1]+1; replace = dp[i-1][j-1]+1. Always take the minimum.

Edit distance is used in spell checkers, DNA sequence alignment, diff tools, and natural language processing for fuzzy string matching.

In the 0/1 Knapsack problem, given items with weights and values and a capacity limit, find the maximum total value that can fit in the knapsack without exceeding capacity. Each item can be included at most once.

Define dp[i][w] as the maximum value using the first i items with capacity w. For each item, either skip it (dp[i-1][w]) or include it (dp[i-1][w-weight[i]] + value[i]) if it fits.

A 1D DP array traversed in reverse achieves O(capacity) space instead of O(n × capacity).

This runs in O(n × capacity) time (pseudo-polynomial).

function knapsack(weights, values, capacity) {
  let dp = 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];
}

Reverse traversal for 0/1: Processing weights from high to low prevents an item from being counted more than once — it ensures we use the previous item row's values.

Unbounded knapsack (each item can be used multiple times) uses the same array but traversed forward, allowing repeated inclusion of the same item.

Determine if an array can be partitioned into two subsets with equal sums. This is equivalent to checking if there is a subset with sum equal to totalSum / 2.

If the total sum is odd, partition is immediately impossible. Otherwise, use a 1D boolean DP array where dp[j] is true if sum j is achievable from the elements processed so far.

For each element, iterate the DP array in reverse (like 0/1 Knapsack) setting dp[j] = dp[j] || dp[j - num].

This runs in O(n × target) time and O(target) space.

function canPartition(nums) {
  let total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  let target = total / 2, dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (let num of nums)
    for (let j = target; j >= num; j--)
      dp[j] = dp[j] || dp[j - num];
  return dp[target];
}

Subset sum reframing: Equal partition reduces to "can we find a subset summing to totalSum/2?" — a classic 0/1 knapsack boolean variant.

Early exit optimization: if dp[target] becomes true during processing, return immediately without completing all remaining iterations.

The Longest Increasing Subsequence (LIS) is the length of the longest subsequence where each element is strictly greater than the previous.

DP approach: dp[i] = LIS ending at index i. For each i, check all j < i where nums[j] < nums[i] and set dp[i] = max(dp[i], dp[j] + 1). This is O(n²).

Patience sorting with binary search achieves O(n log n): maintain a DP "tails" array where tails[i] is the smallest possible tail value for all increasing subsequences of length i+1.

An element extends the LIS if greater than all tails or replaces the first tail that is greater than it (binary search).

function lengthOfLIS(nums) {
  let tails = [];
  for (let num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      let mid = (lo + hi) >> 1;
      tails[mid] < num ? lo = mid + 1 : hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

Patience sort tails: The length of the tails array equals the LIS length. tails is always sorted, enabling binary search for O(log n) per element.

Note: the tails array does not give a valid subsequence directly — to reconstruct the actual LIS, use the O(n²) DP approach with parent pointer tracking.

Count the number of subsets of an array that sum to exactly a target value. Unlike checking existence (partition problem), here you count all such subsets.

Define dp[j] as the count of subsets that sum to j. Initialize dp[0] = 1 (empty subset sums to 0). For each number, iterate j in reverse and add dp[j - num] to dp[j].

This is a counting variant of 0/1 Knapsack — additive instead of max.

Time complexity is O(n × target) and space is O(target).

function countSubsets(nums, target) {
  let dp = Array(target + 1).fill(0);
  dp[0] = 1;
  for (let num of nums)
    for (let j = target; j >= num; j--)
      dp[j] += dp[j - num];
  return dp[target];
}

Additive knapsack: Replace Math.max with += to count all valid combinations instead of finding the optimal one.

This pattern applies to many counting problems: number of ways to make change, number of ways to tile a board, and various combinatorial DP problems.

Unlike maximum sum subarray, a negative number can flip the sign and make a large negative become a large positive when multiplied by another negative.

Track both the maximum and minimum product ending at the current position. The minimum may become the new maximum if the current element is negative.

Update both simultaneously: maxProd = max(num, maxSoFar * num, minSoFar * num) and similarly for minProd.

This runs in O(n) time and O(1) space.

function maxProduct(nums) {
  let max = nums[0], curMax = nums[0], curMin = nums[0];
  for (let i = 1; i < nums.length; i++) {
    let num = nums[i];
    let tempMax = Math.max(num, curMax * num, curMin * num);
    curMin = Math.min(num, curMax * num, curMin * num);
    curMax = tempMax;
    max = Math.max(max, curMax);
  }
  return max;
}

Track min and max simultaneously: A negative element swaps the roles of min and max — the previous minimum (most negative) becomes the basis for the new maximum after multiplication.

A zero in the array resets both curMax and curMin to the current element — products straddle zeros cannot be extended from the previous subarray.

After selling a stock, you must wait one day before buying again (cooldown). Find the maximum profit across any number of transactions under this constraint.

Use three states: held (holding stock), sold (just sold, next day is cooldown), rest (resting, not holding, not in cooldown). Define transitions between states.

At each day: held = max(held, rest - price); sold = held_prev + price; rest = max(rest, sold_prev).

This runs in O(n) time and O(1) space — only three state variables are needed.

function maxProfit(prices) {
  let held = -Infinity, sold = 0, rest = 0;
  for (let price of prices) {
    let prevHeld = held, prevSold = sold;
    held = Math.max(held, rest - price);
    sold = prevHeld + price;
    rest = Math.max(rest, prevSold);
  }
  return Math.max(sold, rest);
}

State machine DP: Model the problem as transitions between states (held/sold/rest) rather than a table — O(1) space captures all needed history in three variables.

The final answer is max(sold, rest) because ending in a cooldown (sold) or idle (rest) state both give valid final profits, while ending held is suboptimal.

Count the number of distinct ways to form string t as a subsequence of string s. Characters can be skipped in s but must appear in the same relative order.

Define dp[i][j] as the number of ways to form t[0..j-1] from s[0..i-1]. If s[i-1] === t[j-1], we either use this character (dp[i-1][j-1]) or skip it (dp[i-1][j]). Otherwise, we must skip: dp[i][j] = dp[i-1][j].

Base case: dp[i][0] = 1 for all i — empty t can always be formed (by selecting nothing).

This runs in O(m × n) time and can be reduced to O(n) space using a single row.

function numDistinct(s, t) {
  let m = s.length, n = t.length;
  let dp = Array(n + 1).fill(0); dp[0] = 1;
  for (let i = 1; i <= m; i++)
    for (let j = n; j >= 1; j--)
      if (s[i-1] === t[j-1]) dp[j] += dp[j-1];
  return dp[n];
}

Reverse iteration for 1D DP: Traversing j backwards prevents reusing the current row's values for the current i, correctly implementing the 2D recurrence.

This problem is a harder variant of the LCS problem — instead of finding the length, you count every distinct matching subsequence.

Given strings s1, s2, and s3, check if s3 is formed by interleaving s1 and s2 while maintaining the relative order of characters from each.

Define dp[i][j] as true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1].

Transitions: dp[i][j] is true if (dp[i-1][j] && s1[i-1]===s3[i+j-1]) or (dp[i][j-1] && s2[j-1]===s3[i+j-1]).

If s1.length + s2.length ≠ s3.length, return false immediately.

function isInterleave(s1, s2, s3) {
  let m = s1.length, n = s2.length;
  if (m + n !== s3.length) return false;
  let dp = Array(n + 1).fill(false); dp[0] = true;
  for (let j = 1; j <= n; j++) dp[j] = dp[j-1] && s2[j-1] === s3[j-1];
  for (let i = 1; i <= m; i++) {
    dp[0] = dp[0] && s1[i-1] === s3[i-1];
    for (let j = 1; j <= n; j++)
      dp[j] = (dp[j] && s1[i-1] === s3[i+j-1]) || (dp[j-1] && s2[j-1] === s3[i+j-1]);
  }
  return dp[n];
}

Two-source DP: The i+j-1 index into s3 is the key insight — at position (i,j), you are checking the character at position i+j in the combined output.

This problem requires O(m × n) state but only O(n) space using the rolling array technique shown above.

Partition a string into the fewest pieces so that every piece is a palindrome. This combines palindrome checking with DP for minimum cuts.

Pre-compute a 2D boolean table: isPalin[i][j] is true if s[i..j] is a palindrome. Then use a 1D DP: dp[i] = minimum cuts for s[0..i].

For each i, if s[0..i] is a palindrome, dp[i] = 0. Otherwise, dp[i] = min(dp[j] + 1) for all j where s[j+1..i] is a palindrome.

This runs in O(n²) time and O(n²) space for the palindrome table.

function minCut(s) {
  let n = s.length;
  let isPalin = Array.from({length: n}, () => Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--)
    for (let j = i; j < n; j++)
      isPalin[i][j] = s[i] === s[j] && (j - i <= 2 || isPalin[i+1][j-1]);
  let dp = Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    if (isPalin[0][i]) { dp[i] = 0; continue; }
    dp[i] = i; // max cuts = i
    for (let j = 1; j <= i; j++)
      if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
  }
  return dp[n-1];
}

Pre-compute palindrome table: Building the O(n²) palindrome table upfront makes each cut decision O(1) lookup, overall reducing what would be O(n³) to O(n²).

The number of cuts is one less than the number of parts — the answer is dp[n-1] which counts cuts, not the number of palindrome pieces.

A digit string can be decoded into letters: '1' → 'A', ..., '26' → 'Z'. Count all possible decodings. Leading zeros and '00' configurations are invalid.

Use 1D DP: dp[i] = number of ways to decode the first i characters. At each position, check if the single digit (i-1) is valid (1-9) and if the two-digit number (i-2 to i-1) is valid (10-26).

Leading zeros (like '06') are invalid — only '10' and '20' are valid two-digit decodings that start with a digit followed by 0.

This runs in O(n) time and O(n) space, reducible to O(1) with two variables.

function numDecodings(s) {
  if (s[0] === '0') return 0;
  let n = s.length, dp = Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    if (s[i-1] !== '0') dp[i] += dp[i-1];
    let two = parseInt(s.substring(i-2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i-2];
  }
  return dp[n];
}

Validate both single and double digit: A single digit of '0' contributes 0 ways (invalid alone); a two-digit value must be 10-26 to be valid — '27' through '99' only decode as two separate digits.

Use O(1) space optimization: only dp[i-1] and dp[i-2] are needed, so replace the array with two variables updated each iteration.