Tracks

Full-Stack Interview Prep

AI Engineering Roadmap →

Dynamic Programming

30 problems · 43 approaches

← Checklist · All topics →

Nth Fibonacci NumberEasy4 approaches

Problem

Return the nth Fibonacci number, where F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2). It is the standard way to show naive recursion → memoisation → tabulation → O(1) space.

Example 1

Input:  n = 10
Output: 55

Also asked as: fibonacci

1. Naive recursion

Time O(2ⁿ)Space O(n)

Direct definition. Recomputes the same subproblems — exponential. State this only as the starting point.

const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));

2. Top-down memoisation

Time O(n)Space O(n)

Cache each fib(k) the first time it is computed.

function fib(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const v = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, v);
  return v;
}

3. Bottom-up table

Time O(n)Space O(n)

Fill dp[0..n] iteratively — no recursion, no stack.

function fib(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

4. Two rolling variables

Time O(n)Space O(1)

Only the last two values matter — O(1) space.

function fib(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}
Coin Change ProblemMedium2 approaches

Problem

Given coin denominations (unlimited supply) and an amount, return the fewest coins that make up the amount, or −1 if it cannot be made. Coin Change II asks instead for the number of distinct combinations.

Example 1

Input:  coins = [1, 2, 5], amount = 11
Output: 3

5 + 5 + 1.

Example 2

Input:  coins = [2], amount = 3
Output: -1

Also asked as: coin change · minimum number of coins

1. Bottom-up (min coins for each amount)

Time O(amount · coins)Space O(amount)

dp[a] = 1 + min over coins c≤a of dp[a−c]. Unbounded knapsack shape.

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

2. Count the number of ways

Time O(amount · coins)Space O(amount)

Different question, same table: iterate coins in the outer loop so combinations aren’t double-counted.

function changeWays(coins, amount) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins)
    for (let a = c; a <= amount; a++)
      dp[a] += dp[a - c];
  return dp[amount];
}
0-1 Knapsack ProblemMedium2 approaches

Problem

n items each have a weight and a value, and the knapsack has capacity W. Take each item whole or not at all. Return the maximum total value whose total weight is at most W.

Example 1

Input:  values = [60, 100, 120], weights = [10, 20, 30], W = 50
Output: 220

Items 2 and 3.

Also asked as: 0/1 knapsack · Knapsack Problem

1. 2-D table

Time O(n · W)Space O(n · W)

dp[i][w] = best value using the first i items within weight w: skip item i, or take it if it fits.

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];
      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][W];
}

2. 1-D rolling array

Time O(n · W)Space O(W)

Only the previous row is needed. Iterate w downward so each item is used at most once.

function knapsack(weights, values, W) {
  const dp = Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let w = W; w >= weights[i]; w--)
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
  return dp[W];
}
Longest Common SubsequenceMedium1 approach

Problem

Return the length of the longest sequence of characters that appears, in order but not necessarily contiguously, in both strings.

Example 1

Input:  a = "abcde", b = "ace"
Output: 3

"ace".

Example 2

Input:  a = "abc", b = "def"
Output: 0

Also asked as: Find the longest common subsequence between two strings

1. 2-D table

Time O(n · m)Space O(n · m)

If the last chars match, +1 on the diagonal; else take the best of dropping one char from either string.

function lcs(a, b) {
  const n = a.length, m = b.length;
  const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; 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[n][m];
}
Longest Increasing SubsequenceMedium2 approaches

Problem

Return the length of the longest strictly increasing subsequence (not necessarily contiguous). The O(n log n) solution is the expected follow-up.

Example 1

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

[2, 3, 7, 101].

1. DP O(n²)

Time O(n²)Space O(n)

dp[i] = longest increasing subsequence ending at i = 1 + max(dp[j]) for j<i with nums[j]<nums[i].

function lengthOfLIS(nums) {
  const dp = Array(nums.length).fill(1);
  let best = 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);
    best = Math.max(best, dp[i]);
  }
  return best;
}

2. Patience sorting + binary search

Time O(n log n)Space O(n)

Maintain `tails`, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. Binary-search the insert point.

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1; else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}
Combinatorial DP — binomial coefficient, Catalan number, derangements, count balanced BSTs of height hMedium1 approach

Problem

Counting problems solved with recurrences, usually modulo 1e9 + 7:

Binomial coefficient C(n, r) (and the permutation coefficient P(n, r)). The nth Catalan number — the number of BSTs with n keys, or of valid parenthesis strings. Derangements — permutations where no element stays in its original position. The number of balanced binary trees of height h.

Example 1

Input:  C(5, 2), Catalan(4), derangements(4)
Output: 10, 14, 9

Also asked as: Binomial CoefficientProblem · Permutation CoefficientProblem · Program for nth Catalan Number · Count Derangements (Permutation such that no element appears in its original position) · Count Balanced Binary Trees of Height h

1. Pascal's triangle / recurrences

Time O(n·k) / O(n²) / O(n)Space O(n·k) / O(n)

C(n,k) = C(n−1,k−1) + C(n−1,k). Catalan Cₙ = Σ Cᵢ·Cₙ₋₁₋ᵢ (or C(2n,n)/(n+1)). Derangements Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂). Balanced BSTs of height h: count(h) = 2·count(h−1)·count(h−2) + count(h−1)².

function binomial(n, k) {
  const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0));
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1;
    for (let j = 1; j <= Math.min(i, k); j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
  }
  return dp[n][k];
}
function catalan(n) {
  const c = new Array(n + 1).fill(0);
  c[0] = 1;
  for (let i = 1; i <= n; i++)
    for (let j = 0; j < i; j++) c[i] += c[j] * c[i - 1 - j];
  return c[n];
}
function derangements(n) {
  if (n <= 1) return n === 0 ? 1 : 0;
  let a = 1, b = 0; // D0, D1
  for (let i = 2; i <= n; i++) [a, b] = [b, (i - 1) * (a + b)];
  return b;
}
function countBalancedBST(h, MOD = 1_000_000_007n) {
  let a = 1n, b = 1n; // count(0), count(1)
  if (h === 0 || h === 1) return 1;
  for (let i = 2; i <= h; i++) {
    const cur = (2n * a * b + b * b) % MOD;
    a = b; b = cur;
  }
  return Number(b);
}
Matrix Chain MultiplicationHard1 approach

Problem

Matrix i has dimensions p[i−1] × p[i]. Choose where to put the parentheses in the product so that the total number of scalar multiplications is as small as possible. Return that minimum.

Example 1

Input:  p = [40, 20, 30, 10, 30]
Output: 26000

(A(BC))D.

Also asked as: Matrix Chain Multiplication

1. Interval DP over split points

Time O(n³)Space O(n²)

dp[i][j] = min scalar multiplications to multiply matrices i..j. Try every split k: dp[i][k] + dp[k+1][j] + p[i-1]·p[k]·p[j].

function matrixChainOrder(p) { // p has length n+1 for n matrices
  const n = p.length - 1;
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
  for (let len = 2; len <= n; len++) {
    for (let i = 1; i + len - 1 <= n; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (cost < dp[i][j]) dp[i][j] = cost;
      }
    }
  }
  return dp[1][n];
}
Fence / tiling recurrences — painting the fence, friends pairing, cut segments, keypad, coin game, score-ways, ways to reach a scoreMedium1 approach

Problem

Short 1-D recurrences:

Painting the fence — n posts and k colours, with no more than two adjacent posts the same colour. Friends pairing — each of n friends stays single or pairs with one other. Maximise cut segments — cut a length n into as many pieces of lengths x, y or z as possible. Mobile keypad — count the n-digit numbers where each next digit is the same key or an adjacent one. Ways to reach a score — using moves of 3, 5 and 10, counting combinations.

Example 1

Input:  fence n = 3, k = 2
Output: 6

Example 2

Input:  friends pairing n = 3
Output: 4

Also asked as: Painting the Fenceproblem · Friends Pairing Problem · Maximize The Cut Segments · Mobile Numeric Keypad Problem · Coin game winner where every player has three choices · Count number of ways to reacha given score in a game · Minimum cost to fill given weight in a bag

1. Linear recurrences

Time O(n)Space O(1)–O(n)

Painting the fence (k colours, no 3 adjacent same): total(i) = (same(i) + diff(i)); same(i) = diff(i−1); diff(i) = (total(i−1))·(k−1). Friends pairing: f(n) = f(n−1) + (n−1)·f(n−2). Cut segments (max pieces of size a/b/c from n): dp[i] = 1 + max(dp[i−a], dp[i−b], dp[i−c]). Ways to reach score with moves {3,5,10}: unbounded-coin-change count.

function paintFence(n, k) {
  if (n === 0) return 0;
  if (n === 1) return k;
  let same = k, diff = k * (k - 1);
  for (let i = 3; i <= n; i++) {
    const prevDiff = diff;
    diff = (same + diff) * (k - 1);
    same = prevDiff;
  }
  return same + diff;
}
function friendsPairing(n) {
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, b + (i - 1) * a];
  return b;
}
function maxCutSegments(n, a, b, c) {
  const dp = new Array(n + 1).fill(-Infinity);
  dp[0] = 0;
  for (let i = 1; i <= n; i++)
    for (const seg of [a, b, c])
      if (i >= seg && dp[i - seg] !== -Infinity) dp[i] = Math.max(dp[i], dp[i - seg] + 1);
  return dp[n] < 0 ? 0 : dp[n];
}
Grid path DP — Gold Mine, Min Cost Path, max square submatrix of 1s, maximum sum rectangleMedium3 approaches

Problem

Grid DP problems:

Gold mine — start anywhere in the first column and move right, up-right or down-right, collecting as much gold as possible. Minimum cost path (Minimum Path Sum) — from the top-left to the bottom-right moving right or down, minimise the sum. Largest square of 1s (Maximal Square). Maximum sum rectangle — the submatrix with the largest sum (Kadane's algorithm over column pairs).

Example 1

Input:  min path sum [[1,3,1], [1,5,1], [4,2,1]]
Output: 7

1→3→1→1→1.

Example 2

Input:  maximal square [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]
Output: 4

Also asked as: Gold Mine Problem · Min Cost PathProblem · Maximum size square sub-matrix with all 1s · Maximum sum rectangle in a 2D matrix · Largest rectangular sub-matrix whose sum is 0 · Largest area rectangular sub-matrix with equal number of 1’s and 0’s · Assembly Line SchedulingProblem

1. Gold mine — DP right-to-left over columns

Time O(R·C)Space O(R·C)

From a cell you move right / right-up / right-down. dp[r][c] = grid[r][c] + max of the three reachable cells in column c+1.

function goldMine(grid) {
  const R = grid.length, C = grid[0].length;
  const dp = grid.map((row) => row.slice());
  for (let c = C - 2; c >= 0; c--)
    for (let r = 0; r < R; r++) {
      const right = dp[r][c + 1];
      const up = r > 0 ? dp[r - 1][c + 1] : 0;
      const down = r < R - 1 ? dp[r + 1][c + 1] : 0;
      dp[r][c] = grid[r][c] + Math.max(right, up, down);
    }
  return Math.max(...dp.map((row) => row[0]));
}

2. Maximum size square submatrix of 1s

Time O(R·C)Space O(R·C)

dp[r][c] = side of the largest all-1s square with its bottom-right corner at (r,c) = 1 + min(top, left, top-left) when grid[r][c] is 1.

function maximalSquare(m) {
  const R = m.length, C = m[0].length;
  const dp = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
  let best = 0;
  for (let r = 1; r <= R; r++)
    for (let c = 1; c <= C; c++)
      if (m[r - 1][c - 1] === 1) {
        dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);
        best = Math.max(best, dp[r][c]);
      }
  return best * best;
}

3. Maximum sum rectangle — Kadane over column ranges

Time O(C²·R)Space O(R)

Fix the left and right column; compress each row between them into a single number (row sum); run 1-D Kadane on that array. O(C²·R).

function maxSumRectangle(mat) {
  const R = mat.length, C = mat[0].length;
  let best = -Infinity;
  for (let left = 0; left < C; left++) {
    const rowSum = new Array(R).fill(0);
    for (let right = left; right < C; right++) {
      for (let r = 0; r < R; r++) rowSum[r] += mat[r][right];
      let cur = 0, localBest = -Infinity;
      for (const x of rowSum) { cur = Math.max(x, cur + x); localBest = Math.max(localBest, cur); }
      best = Math.max(best, localBest);
    }
  }
  return best;
}

Largest submatrix with sum 0 / equal 0s and 1s: same column-pair trick, but instead of Kadane use a prefix-sum→first-index hashmap on the compressed rows to find the widest zero-sum band (map 0→−1 for the 0s/1s version).

Subsequence DP — max sum increasing, longest with adjacent diff one, no three consecutive, alternating, product < K, chain of pairsMedium3 approaches

Problem

Variations on LIS and House Robber:

Maximum sum increasing subsequence. The longest subsequence where adjacent elements differ by exactly 1. The maximum sum with no three consecutive elements taken. The longest alternating (zig-zag) subsequence. The number of subsequences with product less than k. The longest chain of pairs, where (a, b) can be followed by (c, d) only if b < c.

Example 1

Input:  max sum increasing: [1, 101, 2, 3, 100, 4, 5]
Output: 106

1 + 2 + 3 + 100.

Also asked as: Maximum Sum Increasing Subsequence · Longest subsequence such that difference between adjacent is one · Maximum subsequence sum such that no three are consecutive · Longest alternating subsequence · Count all subsequences having product less than K · Maximum Length Chain of Pairs · Maximum Length of Pair Chain · Maximum sum of pairs with specific difference

1. Max Sum Increasing Subsequence

Time O(n²)Space O(n)

Like LIS but dp[i] carries the maximum SUM ending at i: dp[i] = a[i] + max(dp[j]) for j<i with a[j]<a[i].

function maxSumIS(a) {
  const dp = a.slice();
  let best = dp[0] ?? 0;
  for (let i = 1; i < a.length; i++) {
    for (let j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + a[i]);
    best = Math.max(best, dp[i]);
  }
  return best;
}

2. No three consecutive — pick-skip DP

Time O(n)Space O(1)

dp[i] = max(dp[i−1], dp[i−2] + a[i], dp[i−3] + a[i−1] + a[i]) — you may take one or two of any three in a row, never three.

function maxSumNoThreeConsecutive(a) {
  const n = a.length;
  if (n === 0) return 0;
  const dp = new Array(n).fill(0);
  dp[0] = a[0];
  dp[1] = n > 1 ? a[0] + a[1] : dp[0];
  for (let i = 2; i < n; i++)
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i], (i >= 3 ? dp[i - 3] : 0) + a[i - 1] + a[i]);
  return dp[n - 1];
}

3. Longest alternating subsequence & chain of pairs

Time O(n) / O(n log n)Space O(1)

Alternating: track two lengths — one ending on an "up" step, one on a "down" step. Chain of pairs: sort by second element, greedily extend when the next pair’s first exceeds the last chosen second (activity-selection style).

function longestAlternating(a) {
  let up = 1, down = 1;
  for (let i = 1; i < a.length; i++) {
    if (a[i] > a[i - 1]) up = down + 1;
    else if (a[i] < a[i - 1]) down = up + 1;
  }
  return Math.max(up, down);
}
function maxChainOfPairs(pairs) {
  pairs.sort((x, y) => x[1] - y[1]);
  let count = 0, lastEnd = -Infinity;
  for (const [a, b] of pairs) if (a > lastEnd) { count++; lastEnd = b; }
  return count;
}

Longest subsequence with adjacent difference one: dp keyed by value — dp[v] = 1 + max(dp[v−1], dp[v+1]) as you scan. Count subsequences with product < K: 2-D DP dp[i][p] over items and product thresholds. Max sum of pairs with difference exactly D: sort, two pointers, greedily pair.

String DP — longest common substring, LCS of three strings, space-optimised LCS, interleaving, boolean parenthesizationMedium2 approaches

Problem

Two-string (and three-string) DPs:

Longest common substring — must be contiguous in both strings. LCS of three strings. LCS in O(min(m, n)) space. Interleaving String — can s3 be formed by interleaving s1 and s2 while keeping each string's order? Boolean parenthesization — count the ways to parenthesise a T/F expression with & | ^ so that it evaluates to true.

Example 1

Input:  interleave s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2

Input:  longest common substring "ABCDGH", "ACDGHR"
Output: 4 ("CDGH")

Also asked as: Longest Common Substring · LCS (Longest Common Subsequence) of three strings · Space Optimized Solution of LCS · Find if a string is interleaved of two other strings · Boolean Parenthesization Problem

1. Longest common SUBSTRING (contiguous)

Time O(n·m)Space O(m) with a rolling row

dp[i][j] = length of the common suffix of a[..i] and b[..j] = dp[i−1][j−1] + 1 when chars match, else 0. Answer is the max cell.

function longestCommonSubstring(a, b) {
  const m = b.length;
  let prev = new Array(m + 1).fill(0), best = 0;
  for (let i = 1; i <= a.length; i++) {
    const cur = new Array(m + 1).fill(0);
    for (let j = 1; j <= m; j++) {
      if (a[i - 1] === b[j - 1]) { cur[j] = prev[j - 1] + 1; best = Math.max(best, cur[j]); }
    }
    prev = cur;
  }
  return best;
}

2. Is C an interleaving of A and B?

Time O(n·m)Space O(m)

dp[i][j] = can A[..i] + B[..j] form C[..i+j]. dp[i][j] = (A[i−1]===C[i+j−1] && dp[i−1][j]) || (B[j−1]===C[i+j−1] && dp[i][j−1]).

function isInterleave(a, b, c) {
  if (a.length + b.length !== c.length) return false;
  const dp = new Array(b.length + 1).fill(false);
  for (let i = 0; i <= a.length; i++)
    for (let j = 0; j <= b.length; j++) {
      if (i === 0 && j === 0) dp[j] = true;
      else {
        const fromA = i > 0 && a[i - 1] === c[i + j - 1] && dp[j];
        const fromB = j > 0 && b[j - 1] === c[i + j - 1] && dp[j - 1];
        dp[j] = fromA || fromB;
      }
    }
  return dp[b.length];
}

LCS of 3 strings: a 3-D dp[i][j][k]. Space-optimised LCS: keep only the previous row (two 1-D arrays). Boolean parenthesization: interval DP counting the ways an expression of T/F with & | ^ evaluates to true — track (trueCount, falseCount) per interval and combine at each operator.

Knapsack family — 0/1 partition, unbounded, min cost to fill a bag, min removals for rangeMedium2 approaches

Problem

Knapsack variations:

Partition Equal Subset Sum — can the array be split into two parts with equal sums? Unbounded knapsack — each item can be taken any number of times. Minimum cost to fill a bag of exactly W kg, where cost[i] is the price of an i kg packet (−1 means unavailable). Minimum removals so that max − min ≤ k.

Example 1

Input:  partition [1, 5, 11, 5]
Output: true

[1, 5, 5] and [11].

Example 2

Input:  partition [1, 2, 3, 5]
Output: false

Also asked as: Partition problem · Unbounded Knapsack (Repetition of items allowed) · Maximize The Cut Segments · Minimum removals from array to make max –min <= K

1. Partition problem (equal-subset-sum) — boolean subset-sum on total/2

Time O(n·sum)Space O(sum)

If the total is odd, impossible. Otherwise ask "is there a subset summing to total/2?" with the 1-D subset-sum DP.

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

2. Unbounded knapsack

Time O(n·W)Space O(W)

Same table as 0/1 but iterate the weight axis ASCENDING so an item can be reused. dp[w] = max(dp[w], dp[w−weight] + value).

function unboundedKnapsack(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let w = 1; w <= W; w++)
    for (let i = 0; i < weights.length; i++)
      if (weights[i] <= w) dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
  return dp[W];
}

Min cost to fill weight W (costs may be −1 = unavailable): unbounded knapsack minimising cost. Min removals so max−min ≤ K: sort, then it becomes "keep the longest window with a[j]−a[i] ≤ K"; removals = n − that window length.

Egg droppingHard1 approach

Problem

You have e eggs and a building with f floors. An egg breaks when dropped from any floor above an unknown threshold. Return the minimum number of drops that guarantees you find the threshold, in the worst case.

Example 1

Input:  e = 2, f = 10
Output: 4

Example 2

Input:  e = 2, f = 100
Output: 14

Also asked as: Egg Dropping Problem

1. DP over (eggs, floors)

Time O(e·f²)Space O(e·f)

dp[e][f] = min trials to be sure with e eggs and f floors. Drop from floor x: egg breaks → dp[e−1][x−1], survives → dp[e][f−x]; take the worst, minimise over x.

function eggDrop(eggs, floors) {
  const dp = Array.from({ length: eggs + 1 }, () => new Array(floors + 1).fill(0));
  for (let f = 1; f <= floors; f++) dp[1][f] = f;
  for (let e = 2; e <= eggs; e++)
    for (let f = 1; f <= floors; f++) {
      dp[e][f] = Infinity;
      for (let x = 1; x <= f; x++)
        dp[e][f] = Math.min(dp[e][f], 1 + Math.max(dp[e - 1][x - 1], dp[e][f - x]));
    }
  return dp[eggs][floors];
}

O(e·f) version: dp[e][trials] = max floors coverable; increase trials until dp[eggs][trials] ≥ floors.

Game DP — optimal strategy for a game, coin game winnerMedium1 approach

Problem

(1) Optimal strategy: coins are in a row, and two players alternately take a coin from either end. Both play optimally. Return the maximum amount the first player can guarantee. (2) Coin game winner: from a pile of n coins, a player removes 1, x or y coins per turn, and whoever takes the last coin wins. Decide whether the first player wins.

Example 1

Input:  optimal strategy [5, 3, 7, 10]
Output: 15

Take 10, then 5.

Also asked as: Optimal Strategy for a Game · Coin game winner where every player has three choices

1. Interval DP on (i, j) — you pick an end, opponent plays optimally

Time O(n²)Space O(n²)

dp[i][j] = max value the current player can guarantee from coins i..j = max( a[i] + min(dp[i+2][j], dp[i+1][j-1]), a[j] + min(dp[i+1][j-1], dp[i][j-2]) ).

function optimalGame(a) {
  const n = a.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = a[i];
  for (let len = 2; len <= n; len++)
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      const takeLeft = a[i] + Math.min(i + 2 <= j ? dp[i + 2][j] : 0, i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
      const takeRight = a[j] + Math.min(i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0, i <= j - 2 ? dp[i][j - 2] : 0);
      dp[i][j] = Math.max(takeLeft, takeRight);
    }
  return dp[0][n - 1];
}

Coin game with a pile and moves {1, 2, 3}: player loses iff (n mod 4 === 0) for the classic Nim-like variant; in general compute win[i] = OR over moves of !win[i−move].

Optimal BSTHard1 approach

Problem

Sorted keys have search frequencies. Build a BST that minimises the total search cost Σ frequency × depth (the root is at depth 1). Return that cost.

Example 1

Input:  keys = [10, 12, 20], freq = [34, 8, 50]
Output: 142

Also asked as: Optimal Binary Search Tree

1. Interval DP with prefix frequency sums

Time O(n³)Space O(n²)

dp[i][j] = min expected search cost for keys i..j. Try each key r as the root: dp[i][r−1] + dp[r+1][j] + (sum of freq i..j). Every subtree drops one level, so the whole range’s frequency sum is added once per split.

function optimalBST(freq) {
  const n = freq.length;
  const prefix = [0];
  for (const f of freq) prefix.push(prefix[prefix.length - 1] + f);
  const rangeSum = (i, j) => prefix[j + 1] - prefix[i];
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = freq[i];
  for (let len = 2; len <= n; len++)
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let r = i; r <= j; r++) {
        const left = r > i ? dp[i][r - 1] : 0;
        const right = r < j ? dp[r + 1][j] : 0;
        dp[i][j] = Math.min(dp[i][j], left + right + rangeSum(i, j));
      }
    }
  return dp[0][n - 1];
}
Palindrome partitioning — minimum cutsHard1 approach

Problem

Return the minimum number of cuts needed to split the string into pieces that are all palindromes.

Example 1

Input:  "aab"
Output: 1

"aa" | "b".

Example 2

Input:  "ababbbabbababa"
Output: 3

Also asked as: Palindrome PartitioningProblem

1. Precompute isPalindrome, then 1-D cut DP

Time O(n²)Space O(n²)

pal[i][j] via interval DP. cuts[i] = min cuts for s[0..i]; if s[j..i] is a palindrome, cuts[i] = min(cuts[i], cuts[j−1] + 1), with cuts[−1] = −1.

function minCut(s) {
  const n = s.length;
  const pal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--)
    for (let j = i; j < n; j++)
      pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);
  const cuts = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    if (pal[0][i]) { cuts[i] = 0; continue; }
    cuts[i] = i;
    for (let j = 1; j <= i; j++)
      if (pal[j][i]) cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
  }
  return cuts[n - 1];
}
Largest Independent Set in a treeMedium1 approach

Problem

Return the size of the largest set of tree nodes in which no two nodes are connected by an edge (no parent–child pair). With node values instead of counts, this is House Robber III.

Example 1

Input:  10 with children 20, 30; 20 has children 40, 50; 30 has right child 60; 50 has children 70, 80
Output: 5

{10, 40, 60, 70, 80}.

Also asked as: Largest Independent Set Problem

1. Tree DP — include vs exclude each node

Time O(n)Space O(h)

inc(node) = 1 + Σ exc(child); exc(node) = Σ max(inc(child), exc(child)). Answer = max(inc(root), exc(root)).

function largestIndependentSet(node) {
  if (!node) return { inc: 0, exc: 0 };
  const L = largestIndependentSet(node.left);
  const R = largestIndependentSet(node.right);
  return {
    inc: 1 + L.exc + R.exc,
    exc: Math.max(L.inc, L.exc) + Math.max(R.inc, R.exc),
  };
}
// answer: const r = largestIndependentSet(root); return Math.max(r.inc, r.exc);
Best time to buy and sell a stock at most K timesHard1 approach

Problem

prices[i] is the price on day i. Complete at most k transactions, never holding more than one share at a time. Return the maximum profit.

Example 1

Input:  k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7

Buy at 2, sell at 6; buy at 0, sell at 3.

Also asked as: Maximum profit by buying and selling a share at most k times

1. DP over (transactions, day), O(k·n)

Time O(k·n)Space O(n)

dp[t][d] = max profit using ≤ t transactions up to day d = max(dp[t][d−1], price[d] + best) where best = max over m<d of (dp[t−1][m] − price[m]) — maintained incrementally.

function maxProfitK(k, prices) {
  const n = prices.length;
  if (!n) return 0;
  if (k >= n / 2) { // unlimited transactions
    let profit = 0;
    for (let i = 1; i < n; i++) if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    return profit;
  }
  const dp = Array.from({ length: k + 1 }, () => new Array(n).fill(0));
  for (let t = 1; t <= k; t++) {
    let best = -prices[0];
    for (let d = 1; d < n; d++) {
      dp[t][d] = Math.max(dp[t][d - 1], prices[d] + best);
      best = Math.max(best, dp[t - 1][d] - prices[d]);
    }
  }
  return dp[k][n - 1];
}
Smallest sum contiguous subarray / max difference of zeros and ones in a binary stringEasy1 approach

Problem

(1) Return the smallest sum of any contiguous subarray (Kadane's algorithm with min). (2) In a binary string, find the substring that maximises (number of 0s) − (number of 1s), or −1 if the string is all 1s.

Example 1

Input:  smallest sum [3, -4, 2, -3, -1, 7, -5]
Output: -6

[-4, 2, -3, -1].

Example 2

Input:  zeros − ones "11000010001"
Output: 6

Also asked as: Smallest sum contiguous subarray · Maximum difference of zeros and ones in binary string

1. Kadane, minimising (or on a transformed array)

Time O(n)Space O(1)

Smallest sum: run Kadane keeping the minimum running sum. Max (#0 − #1) over any substring: map 0→+1, 1→−1 and run standard maximum-subarray Kadane.

function smallestSubarraySum(a) {
  let cur = a[0], best = a[0];
  for (let i = 1; i < a.length; i++) {
    cur = Math.min(a[i], cur + a[i]);
    best = Math.min(best, cur);
  }
  return best;
}
function maxZeroMinusOne(bits) {
  let cur = 0, best = 0, any = false;
  for (const ch of bits) {
    any = true;
    cur = Math.max(ch === '0' ? 1 : -1, cur + (ch === '0' ? 1 : -1));
    best = Math.max(best, cur);
  }
  return any ? Math.max(best, -1) : 0; // -1 if the string is all 1s
}
Longest Palindromic SubsequenceMedium1 approach

Problem

Return the length of the longest subsequence (not necessarily contiguous) that is a palindrome.

Example 1

Input:  "bbbab"
Output: 4

"bbbb".

Example 2

Input:  "cbbd"
Output: 2

Also asked as: Longest Palindromic Subsequence

1. LCS of the string and its reverse

Time O(n²)Space O(n²)

The longest subsequence that reads the same forwards and backwards is exactly the LCS of s and reverse(s).

function longestPalindromeSubseq(s) {
  const r = [...s].reverse().join('');
  const n = s.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = s[i - 1] === r[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[n][n];
}

Direct interval DP also works: dp[i][j] = 2 + dp[i+1][j-1] if s[i]===s[j], else max(dp[i+1][j], dp[i][j-1]).

Climbing StairsEasy1 approach

Problem

You climb a staircase of n steps, taking 1 or 2 steps at a time. Return the number of distinct ways to reach the top.

Example 1

Input:  n = 3
Output: 3

1+1+1, 1+2, 2+1.

1. Two rolling variables

Time O(n)Space O(1)

ways(i) = ways(i − 1) + ways(i − 2): the last step was 1 or 2. It is Fibonacci.

function climbStairs(n) {
  let a = 1, b = 1; // ways(0), ways(1)
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
House Robber IIMedium1 approach

Problem

Houses stand in a circle, so the first and last are neighbours. You cannot rob two adjacent houses. Return the maximum amount you can rob.

Example 1

Input:  [2, 3, 2]
Output: 3

Houses 0 and 2 are adjacent in the circle.

Example 2

Input:  [1, 2, 3, 1]
Output: 4

1. Two linear runs

Time O(n)Space O(1)

Houses form a circle, so the first and last cannot both be robbed. Answer = max(rob 0..n−2, rob 1..n−1) using the linear House Robber.

function rob(nums) {
  if (nums.length === 1) return nums[0];
  const line = (lo, hi) => {
    let prev = 0, cur = 0;
    for (let i = lo; i <= hi; i++) [prev, cur] = [cur, Math.max(cur, prev + nums[i])];
    return cur;
  };
  return Math.max(line(0, nums.length - 2), line(1, nums.length - 1));
}
Coin Change IIMedium1 approach

Problem

Given coin denominations (unlimited supply) and an amount, return the number of combinations that make up the amount. Order does not matter: 1+2 and 2+1 are the same combination.

Example 1

Input:  amount = 5, coins = [1, 2, 5]
Output: 4

5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

1. Unbounded knapsack, coins in the outer loop

Time O(amount × coins)Space O(amount)

dp[a] = ways to make a. Looping coins outside counts combinations (each order once); looping amounts outside would count permutations.

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins)
    for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
  return dp[amount];
}

The loop order is the whole trick — be ready to explain it.

Decode WaysMedium1 approach

Problem

Letters are encoded as numbers: A = 1, …, Z = 26. Given a digit string, return how many ways it can be decoded. "06" is not a valid code, so a 0 can only appear as part of 10 or 20.

Example 1

Input:  "12"
Output: 2

"AB" (1, 2) or "L" (12).

Example 2

Input:  "226"
Output: 3

Example 3

Input:  "06"
Output: 0

1. Rolling DP over prefixes

Time O(n)Space O(1)

ways(i) takes ways(i − 1) if s[i−1] is 1–9, plus ways(i − 2) if s[i−2..i−1] is 10–26. A "0" can only be the second digit of 10 or 20.

function numDecodings(s) {
  let prev2 = 1, prev1 = s[0] === '0' ? 0 : 1;
  for (let i = 2; i <= s.length; i++) {
    let cur = 0;
    if (s[i - 1] !== '0') cur += prev1;
    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) cur += prev2;
    [prev2, prev1] = [prev1, cur];
  }
  return prev1;
}
Best Time to Buy and Sell Stock with CooldownMedium1 approach

Problem

You may make as many transactions as you like, holding at most one share at a time. After selling, you cannot buy on the next day (a one-day cooldown). Return the maximum profit.

Example 1

Input:  [1, 2, 3, 0, 2]
Output: 3

Buy, sell, cooldown, buy, sell.

1. State machine: hold / sold / rest

Time O(n)Space O(1)

hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold of yesterday). Buying needs yesterday to be rest, which enforces the cooldown.

function maxProfit(prices) {
  let hold = -Infinity, sold = 0, rest = 0;
  for (const p of prices) {
    const prevSold = sold;
    sold = hold + p;
    hold = Math.max(hold, rest - p);
    rest = Math.max(rest, prevSold);
  }
  return Math.max(sold, rest);
}
Unique PathsMedium2 approaches

Problem

A robot starts at the top-left of an m × n grid and moves only right or down. Return the number of distinct paths to the bottom-right corner.

Example 1

Input:  m = 3, n = 7
Output: 28

Example 2

Input:  m = 3, n = 2
Output: 3

1. 1-D rolling row

Time O(m·n)Space O(n)

paths(r, c) = paths(r − 1, c) + paths(r, c − 1). One row suffices: row[c] += row[c − 1].

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++)
    for (let c = 1; c < n; c++) row[c] += row[c - 1];
  return row[n - 1];
}

2. Combinatorics

Time O(min(m, n))Space O(1)

Choose which m − 1 of the m + n − 2 moves go down: C(m + n − 2, m − 1).

function uniquePaths(m, n) {
  let res = 1;
  for (let i = 1; i < m; i++) res = (res * (n - 1 + i)) / i;
  return Math.round(res);
}
Palindromic SubstringsMedium1 approach

Problem

Return the number of palindromic substrings. Substrings at different positions count separately, even when their text is the same.

Example 1

Input:  "abc"
Output: 3

Example 2

Input:  "aaa"
Output: 6

a, a, a, aa, aa, aaa.

1. Expand around every centre

Time O(n²)Space O(1)

There are 2n − 1 centres (each char and each gap). Expand while the ends match, counting each step.

function countSubstrings(s) {
  let count = 0;
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) { count++; l--; r++; }
  };
  for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }
  return count;
}

The DP table (dp[i][j] = s[i] === s[j] && dp[i+1][j−1]) is also O(n²) but uses O(n²) space.

Target SumMedium1 approach

Problem

Put either + or − in front of every number, then add them all up. Return how many sign assignments give exactly target.

Example 1

Input:  nums = [1, 1, 1, 1, 1], target = 3
Output: 5

Exactly one of the five numbers is negative.

1. Reduce to subset-sum counting

Time O(n × sum)Space O(sum)

Let P be the "+" set: P − (total − P) = target, so P = (total + target) / 2. Count subsets with that sum (0/1 knapsack, iterate sums downward).

function findTargetSumWays(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > total || (total + target) % 2) return 0;
  const P = (total + target) / 2;
  const dp = new Array(P + 1).fill(0);
  dp[0] = 1;
  for (const x of nums)
    for (let s = P; s >= x; s--) dp[s] += dp[s - x];
  return dp[P];
}

Start with memoised recursion on (index, running sum) if the algebra does not come to you.

Burst BalloonsHard1 approach

Problem

Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbours (out-of-range neighbours count as 1). Burst every balloon in the best order and return the maximum coins.

Example 1

Input:  [3, 1, 5, 8]
Output: 167

Burst 1, 5, 3, 8: 15 + 120 + 24 + 8.

1. Interval DP on the last balloon burst

Time O(n³)Space O(n²)

Pad with 1s. dp[l][r] = best coins bursting everything strictly between l and r. Choosing k as the LAST to burst in (l, r) makes its neighbours exactly l and r, so the two sides are independent.

function maxCoins(nums) {
  const a = [1, ...nums, 1], n = a.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 2; len < n; len++) {
    for (let l = 0; l + len < n; l++) {
      const r = l + len;
      for (let k = l + 1; k < r; k++)
        dp[l][r] = Math.max(dp[l][r], dp[l][k] + a[l] * a[k] * a[r] + dp[k][r]);
    }
  }
  return dp[0][n - 1];
}

Thinking "first to burst" fails because neighbours change — "last to burst" is the key insight.

Regular Expression MatchingHard1 approach

Problem

Implement pattern matching where "." matches any single character and "*" matches zero or more of the element just before it. The pattern must match the entire string.

Example 1

Input:  s = "aa", p = "a"
Output: false

Example 2

Input:  s = "aa", p = "a*"
Output: true

Example 3

Input:  s = "aab", p = "c*a*b"
Output: true

1. Memoised recursion on (i, j)

Time O(|s|·|p|)Space O(|s|·|p|)

first = s[i] matches p[j] (or "."). If p[j+1] is "*", either skip "x*" (j + 2) or consume one char if first matches (i + 1). Otherwise require first and advance both.

function isMatch(s, p) {
  const memo = new Map();
  const dp = (i, j) => {
    const key = i * (p.length + 1) + j;
    if (memo.has(key)) return memo.get(key);
    let ans;
    if (j === p.length) ans = i === s.length;
    else {
      const first = i < s.length && (p[j] === s[i] || p[j] === '.');
      if (p[j + 1] === '*') ans = dp(i, j + 2) || (first && dp(i + 1, j));
      else ans = first && dp(i + 1, j + 1);
    }
    memo.set(key, ans);
    return ans;
  };
  return dp(0, 0);
}