Dynamic programming

Count the ways to climb n steps taking one or two at a time.

Trigger

'How many ways' plus a small fixed set of moves.

Approach

1. Write the recurrence out loud: ways(n) = ways(n−1) + ways(n−2).
2. Base cases: ways(0) = ways(1) = 1.
3. It is Fibonacci — say so, it shows you recognise the shape.
4. Two variables instead of an array: O(1) space.

Target complexity

O(n) time, O(1) space.

Pitfall

Getting the base cases wrong. Check n = 1 and n = 2 by hand before running.

Say it out loud

“The last step was either one or two, so the count is the sum of the two previous counts — this is Fibonacci. I only ever look one and two steps back, so I'll keep two variables instead of an array and get constant space.”

Solve on LeetCode

Return the set-bit count for every integer from 0 to n.

Trigger

'For every number up to n' — a DP over bit patterns.

Approach

1. Calling popcount n times is O(n log n). Say it, then improve.
2. DP: dp[i] = dp[i >> 1] + (i & 1). Shifting right removes the last bit, which I add back.
3. The subproblem is always smaller, so a single forward pass works.

Target complexity

O(n) time, O(n) space for the output.

Pitfall

Not recognising that this is DP. Recomputing popcount per number is the answer that scores lower.

Say it out loud

“This is DP over bit patterns: the count for i is the count for i shifted right, plus its last bit. Every subproblem is strictly smaller, so one forward pass fills the table — linear rather than n log n.”

Solve on LeetCode

Generate the first n rows of Pascal's triangle.

Trigger

'Pascal', 'binomial coefficients', 'each element is the sum of the two above'.

Approach

1. The recurrence is the definition: C(n,k) = C(n−1,k−1) + C(n−1,k).
2. Build each row from the previous one, with ones at both ends.
3. Connect it to combinatorics: row n is the binomial coefficients.

Target complexity

O(n²) time and space — the output itself is quadratic.

Pitfall

Off-by-one at the row edges. Trace row three by hand before you run it.

Say it out loud

“This is the binomial recurrence written out, so each row builds from the previous one. Worth noting the output itself is quadratic in size, so O(n squared) is the floor here, not a weakness of the approach.”

Solve on LeetCode

Find the minimum number of coins summing to an amount, with unlimited coins of each type.

Trigger

'Fewest coins', 'minimum items to reach a total' — unbounded knapsack.

Approach

1. State: dp[a] = fewest coins to make amount a. Initialise to infinity, dp[0] = 0.
2. Transition: for each amount, try every coin — dp[a] = min(dp[a], dp[a − c] + 1).
3. Say why greedy fails: coins [1, 3, 4] and amount 6 gives 4+1+1 greedily but 3+3 is optimal.

Target complexity

O(amount × coins) time, O(amount) space.

Pitfall

Reaching for greedy. It only works for canonical coin systems, and the interviewer will pick one where it does not.

Say it out loud

“Greedy would take the largest coin first, but that's only optimal for canonical systems — with coins one, three and four and a target of six, greedy gives three coins and the answer is two. So it's DP over the amount, and the loop order makes each coin reusable, which is what unbounded means.”

Solve on LeetCode

Count the ways to decode a digit string where 1–26 map to letters.

Trigger

'How many decodings', 'ways to parse a string with a mapping'.

Approach

1. State: dp[i] = decodings of the prefix of length i.
2. Transition: add dp[i−1] if the single digit is valid (not zero), and dp[i−2] if the two-digit number is 10 to 26.
3. Zeros are the whole difficulty: '0' alone is invalid, '10' and '20' are valid, '30' is not.

Target complexity

O(n) time, O(1) space with two variables.

Pitfall

Mishandling zeros. Test '0', '06', '10', '100' by hand — that is where it breaks.

Say it out loud

“It's Fibonacci-shaped with validity conditions on each term. The real work is the zeros: a zero can never stand alone, and it's only valid as the second digit of ten or twenty. I'll trace those cases by hand before I claim it's done.”

Solve on LeetCode

Find the minimum number of insertions, deletions and substitutions to turn one string into another.

Trigger

'Edit distance', 'minimum operations to transform', spell-checking.

Approach

1. State: dp[i][j] = distance between the two prefixes.
2. Base cases: transforming from or to an empty string costs the other length.
3. Transition: if the characters match, carry dp[i−1][j−1]; otherwise 1 + min of the three neighbours, and name which operation each neighbour is.
4. Row reduction to O(m) space.

Target complexity

O(n × m) time, O(min(n, m)) space.

Pitfall

Not initialising the first row and column. It is the most common DP bug there is.

Say it out loud

“Each cell is the cost of aligning two prefixes. The three neighbours map onto the three operations — delete, insert, substitute — so the transition writes itself once the state is clear. The part I'll be careful with is the base row and column, which encode transforming to and from the empty string.”

Solve on LeetCode

Maximise the sum of a subsequence with no two adjacent elements.

Trigger

'Cannot take two neighbours', 'maximise without adjacency'.

Approach

1. State: dp[i] = the best achievable considering the first i houses.
2. Transition: dp[i] = max(dp[i−1], dp[i−2] + value[i]) — skip it or take it.
3. Roll the array down to two variables.

Target complexity

O(n) time, O(1) space.

Pitfall

Assuming greedy works. Taking every other house is not optimal — [2, 1, 1, 2] proves it.

Say it out loud

“The decision at each house is take it or skip it, and taking it forbids the previous one. That gives me a two-term recurrence, so it's linear time and I can roll it into two variables. Greedy fails here — two-one-one-two is the counterexample.”

Solve on LeetCode

Decide whether you can reach the last index, given a maximum jump length at each position.

Trigger

'Can you reach the end', 'maximum jump at each step'.

Approach

1. DP works: reachable[i] from any earlier reachable j with reach — O(n²).
2. Greedy is better: track the furthest index reachable so far; if i ever exceeds it, fail.
3. This is one of the cases where greedy provably beats DP — say why.

Target complexity

O(n) time, O(1) space greedily.

Pitfall

Writing the O(n²) DP and stopping there. The greedy is the expected answer.

Say it out loud

“The DP is quadratic, but here greedy is provably correct: I sweep left to right tracking the furthest reachable index, and I fail the moment my position passes it. The exchange argument is that reaching further is never worse, so there's no reason to prefer a shorter jump.”

Solve on LeetCode

Find the length of the longest subsequence common to two strings.

Trigger

Two strings plus 'common', 'shared', 'alignment'.

Approach

1. State: dp[i][j] = LCS of the first i characters of A and the first j of B.
2. Transition: if the characters match, 1 + dp[i−1][j−1]; otherwise max of dropping one side.
3. Row-by-row space reduction to O(min(n, m)).

Target complexity

O(n × m) time, O(min(n, m)) space after the reduction.

Pitfall

Confusing subsequence with substring. Subsequences need not be contiguous.

Say it out loud

“The state is the pair of prefixes. If the two characters match I take them and move both pointers; otherwise I take the better of dropping one. Each row only depends on the previous one, so I can drop the table to two rows.”

Solve on LeetCode

Find the length of the longest strictly increasing subsequence.

Trigger

'Longest increasing subsequence', or anything reducible to it.

Approach

1. O(n²) DP first: dp[i] = the best ending at i, scanning all j < i.
2. Then the O(n log n) version: keep an array of the smallest tail for each length.
3. For each value, binary search the position it replaces. The array's length is the answer.
4. Be explicit: that array is not the subsequence, only its lengths.

Target complexity

O(n log n) time, O(n) space.

Pitfall

Claiming the tails array is the actual subsequence. It is not; reconstructing needs parent pointers.

Say it out loud

“The straightforward DP is quadratic. The n-log-n version keeps, for each length, the smallest possible tail — and binary searches where each new value belongs. Worth saying: that array isn't a valid subsequence, it's a set of best-case tails, so reconstructing the actual sequence needs back-pointers.”

Solve on LeetCode

Find the contiguous subarray with the largest sum.

Trigger

'Maximum contiguous sum', values can be negative.

Approach

1. Brute force O(n²) over all start-end pairs. Say it, then improve.
2. Kadane: at each element, either extend the current run or start fresh from here.
3. cur = max(x, cur + x); best = max(best, cur).
4. Mention divide and conquer as the O(n log n) alternative, since it is the follow-up.

Target complexity

O(n) time, O(1) space.

Pitfall

Initialising `best` to zero. With an all-negative array the answer is the least negative element, not zero.

Say it out loud

“This is Kadane, which is really DP with a one-element state: the best sum ending here is either this element alone or this element plus the best ending before it. I'll initialise from the first element rather than zero, so an all-negative array still gives the right answer.”

Solve on LeetCode

Decide whether an array can be split into two subsets with equal sums.

Trigger

'Split into two equal halves', 'is there a subset summing to X' — subset sum.

Approach

1. Total must be even, otherwise return false immediately.
2. Reduce to: is there a subset summing to total/2? That is subset sum, which is NP-complete.
3. Pseudo-polynomial DP: a boolean array over reachable sums, iterated downwards per item.
4. Say the iteration direction and why: descending prevents reusing the same item twice.

Target complexity

O(n × sum) time, O(sum) space.

Pitfall

Iterating the inner loop upwards, which silently turns 0/1 knapsack into unbounded knapsack.

Say it out loud

“This is subset sum, which is NP-complete, but the DP is pseudo-polynomial in the target so it's fine at these sizes. The detail that matters is iterating the sums downwards — going upwards would let me use the same element twice and turn it into the unbounded version.”

Solve on LeetCode

Count the ways to assign plus and minus to each number so the total equals a target.

Trigger

'Assign signs', 'plus or minus each element' — subset sum in disguise.

Approach

1. Rewrite the algebra: if P is the positive subset and N the negative, P − N = target and P + N = total. So P = (target + total) / 2.
2. That turns it into: how many subsets sum to P? Classic subset sum counting.
3. Guard: if (target + total) is odd or negative, the answer is zero.

Target complexity

O(n × sum) time, O(sum) space.

Pitfall

Going straight to exponential enumeration of sign assignments without spotting the reduction.

Say it out loud

“The signed sum can be rewritten: the positive subset minus the negative one is the target, and together they're the total. Solving those two gives me a single target for the positive subset, so this is subset-sum counting — which is polynomial in the sum instead of exponential in n.”

Solve on LeetCode

Count the lattice paths from the top-left to the bottom-right of a grid, moving only right and down.

Trigger

'How many paths in a grid' with restricted moves.

Approach

1. DP: dp[i][j] = dp[i−1][j] + dp[i][j−1], with the first row and column all ones.
2. One row of space is enough.
3. Then give the closed form: every path is m−1 downs and n−1 rights, so it is C(m+n−2, m−1).

Target complexity

O(m × n) with DP, or O(min(m,n)) with the combinatorial formula.

Pitfall

Not spotting that it is a combinatorics problem. The closed form is a free extra point.

Say it out loud

“The DP is two lines, but there's a closed form: every path is the same multiset of moves in some order, so it's m plus n minus two choose m minus one. I'd write the DP because it generalises to obstacles, but I'd mention the formula.”

Solve on LeetCode

Decide whether a string can be segmented into words from a dictionary.

Trigger

'Can this be split into valid pieces', 'segment the string'.

Approach

1. State: dp[i] = can the prefix of length i be segmented?
2. Transition: dp[i] is true if some j < i has dp[j] true and s[j:i] in the dictionary.
3. Put the dictionary in a set for O(1) lookup.
4. Bound the inner loop by the longest word to cut constant factors.

Target complexity

O(n² × L) time, O(n) space.

Pitfall

Greedy longest-match. 'aaaaab' with words ['aaaa', 'aaa', 'b'] breaks it.

Say it out loud

“Greedy longest-match fails — I can consume a prefix that makes the rest unsegmentable. So it's DP over prefixes: position i is reachable if some earlier reachable position is followed by a dictionary word. The dictionary goes in a set so the membership check is constant.”

Solve on LeetCode

Maximise the coins from bursting balloons, where each burst's value depends on its current neighbours.

Trigger

An interval problem where the order of operations changes the values.

Approach

1. The trap: thinking forwards. Which balloon you burst first changes everything after it.
2. Invert it — think about which balloon is burst **last** in a range. Then its neighbours are the range boundaries, which are fixed.
3. State: dp[i][j] = the best over the open interval (i, j). Transition: pick the last balloon k.
4. Pad the array with ones at both ends to remove the boundary cases.

Target complexity

O(n³) time, O(n²) space.

Pitfall

Defining the state as 'first balloon burst'. The subproblems then are not independent and the recurrence does not close.

Say it out loud

“The obvious framing — which do I burst first — doesn't decompose, because bursting changes the neighbours of everything left. If instead I ask which balloon is burst *last* in a range, its neighbours are exactly the range boundaries, which are fixed. That makes the subproblems independent and gives an interval DP.”

Solve on LeetCode