Dynamic Programming

1The mental model (what this really is)#

Dynamic programming is one idea wearing a scary costume.

• Solve a big problem by solving smaller versions of the same problem.
• Never solve the same small version twice.
• That is the whole thing. Two parts, below.

Part one: the problem breaks into subproblems that look like the original, just smaller.

• "Smallest cost to reach step n" depends on "smallest cost to reach step n-1." Same shape, smaller input.
• That property is called optimal substructure.
• If it does not hold, no amount of caching saves you.

Part two: those subproblems overlap.

• Draw the recursion tree for naive Fibonacci and fib(40) calls fib(38) twice, fib(37) three times, blowing up to about 2^40 calls.
• "Smallest cost to reach step 5" gets asked hundreds of times inside a naive recursion.
• DP says: compute it once, write the answer down, reuse it.
• That single move drops exponential work to linear.

The write-it-down part is the trick.

• People think DP is about clever math. It is not.
• It is about caching the answers to subproblems. Everything else is bookkeeping.

2How to recognize it (the signals in a problem)#

Nobody tells you "this is DP." You have to smell it in the first 60 seconds. Here are the signals I react to instantly.

• The prompt asks for an optimum over choices. "Maximum," "minimum," "longest," "fewest," "best," especially when at every step you pick from a few options and the picks interact.
• It asks "how many ways." Counting valid arrangements, paths, or partitions is almost always DP. "How many ways to climb n stairs taking 1 or 2 at a time" is Fibonacci in disguise.
• "Can you reach / is it possible." Boolean feasibility, like "can this array split into two subsets with equal sum," is DP. The table holds true or false instead of a number.
• You want to try every combination, and that brute force would be exponential (2^n subsets, n! orderings). DP is usually the upgrade that kills the blowup and gets you to polynomial time.
• Each decision affects future decisions, so you cannot greedily grab the best local move. If greedy feels wrong or you can build a small counterexample in your head, think DP.

One honest warning: not every "maximum" problem is DP.

• "Maximum element in an array" is a scan.
• "Maximum meetings you can attend" is greedy by end time.
• The real tell is when a choice now changes what is optimal later, and the same situations keep recurring. When both are true, reach for DP.

3The template (how it works, with pseudocode)#

I solve every DP the same way, in the same order. Do not skip steps. The order is what keeps you calm when the clock is running and the interviewer is watching your cursor.

1. Define the state. Write a literal sentence: dp[i] = the answer to the subproblem described by i. Be precise. This is 80% of the work and the one step people skip under pressure.
2. Write the recurrence. How does dp[i] depend on smaller states? This is the choice you make at step i, written as math.
3. Set the base cases. The smallest subproblems you can answer directly with no recursion.
4. Decide the order. Top-down (recursion plus memo) or bottom-up (fill a table). Make sure every dependency is ready before you read it.
5. Read off the answer. Which cell holds the final result? Sometimes dp[n], sometimes dp[n-1], sometimes the max over the whole table.

Here is the shape I write first, every time. Top-down, because it maps one-to-one onto the recurrence I just spoke out loud.

memo = {}

def solve(state):
 if state is a base case:
 return base value
 if state in memo:
 return memo[state]

 best = worst_possible_value
 for each choice available at state:
 result = combine(choice, solve(smaller_state))
 best = better_of(best, result)

 memo[state] = best
 return best

answer = solve(initial_state)

Once that works, I often convert it to bottom-up for speed, to drop the recursion call overhead, and to avoid blowing the stack on large inputs:

dp = table sized by all states
initialize base cases
for state in dependency_order:
 dp[state] = combine over choices using already-filled dp[...]
return dp[final_state]

Start top-down in the interview.

• It is easier to get right, and the memo is a one-line change.
• You can narrate the recurrence out loud as you write it.
• Convert to a table only if asked, if you need the extra speed, or if recursion depth could overflow (for example, amount up to 10^5).

4A worked example (walk through one problem step by step)#

Coin Change: given coin denominations and a target amount, find the fewest coins that sum to the amount. Return -1 if impossible.

• Classic, asked at Amazon and Google.
• It teaches the whole pattern in one shot.
• Say coins are [1, 3, 4] and the amount is 6.

Step 1, define the state.

• dp[x] = the minimum number of coins needed to make exactly amount x.
• The state is a single number, the remaining amount.
• One integer fully describes any subproblem, which already tells me the table has only A + 1 cells.

Step 2, the recurrence.

• To make amount x, my only real choice is which coin I use last.
• If I use a coin of value c, I still had to make amount x - c first, which costs dp[x - c] coins, plus the one coin I just spent.
• I try every coin and keep the best.

dp[x] = 1 + min( dp[x - c] for every coin c where x - c >= 0 )

Step 3, base case.

• dp[0] = 0: it takes zero coins to make amount zero.
• Everything else starts at "infinity," meaning not yet reachable, until a coin proves otherwise.

Step 4, order.

• To compute dp[x] I need strictly smaller amounts, so I fill from 0 up to 6.
• Dependencies are always ready by the time I reach them.

Step 5, fill it in.

• dp[0] = 0.
• dp[1]: use coin 1, need dp[0]=0, so 1 + 0 = 1. Coins 3 and 4 are too big. dp[1] = 1.
• dp[2]: only coin 1 fits, 1 + dp[1] = 2. dp[2] = 2.
• dp[3]: coin 1 gives 1 + dp[2] = 3. Coin 3 gives 1 + dp[0] = 1. Best is 1. dp[3] = 1.
• dp[4]: coin 1 gives 1 + dp[3] = 2. Coin 3 gives 1 + dp[1] = 2. Coin 4 gives 1 + dp[0] = 1. Best is 1. dp[4] = 1.
• dp[5]: coin 1 gives 1 + dp[4] = 2. Coin 3 gives 1 + dp[2] = 3. Coin 4 gives 1 + dp[1] = 2. Best is 2. dp[5] = 2.
• dp[6]: coin 1 gives 1 + dp[5] = 3. Coin 3 gives 1 + dp[3] = 2. Coin 4 gives 1 + dp[2] = 3. Best is 2. dp[6] = 2.

Answer: 2 coins. That is 3 + 3. At the end, if dp[6] were still infinity, I return -1, which is the edge case interviewers probe.

Notice what happened.

• I never tried every combination of coins, which would have been exponential.
• I built up from the bottom, each amount reusing answers I already had.
• The naive recursive version recomputes dp[3] dozens of times across the tree; the memo computes it once and reads it back in O(1) after that.
• The rhythm to internalize so it is automatic: state, choice, base case, order, read the answer.

5Variations and gotchas#

Once you see the one-dimensional version, the whole family opens up. Most "new" problems are just one of these in a costume.

• 1D over an array or amount. Coin Change, climbing stairs, house robber. State is one index or one number. Usually O(n) or O(A) cells.
• 2D grid DP. Unique paths, minimum path sum, edit distance. State is a pair (i, j), usually two string positions or grid coordinates. The recurrence looks at the 2 or 3 neighbors you can come from.
• Subsequence DP. Longest common subsequence, longest increasing subsequence. Often 2D dp[i][j] over two sequences, or 1D dp[i] meaning "best ending at index i." LIS has a slick O(n log n) version with binary search that interviewers love to see once you have the O(n^2) one.
• Knapsack family. You have a capacity and items, each with a cost and value. Subset-sum, partition, and target-sum problems are all this in costume. Watch whether each item can be used once (0/1 knapsack) or many times (unbounded). That single detail flips your inner loop direction.
• Interval DP. Burst balloons, matrix chain multiplication. State is a range (left, right) and you pick a split point or a "last" element inside the range. Genuinely hard and usually O(n^3). Recognize them by "do something to a subarray and the boundaries interact."
• DP on trees and DP with bitmask state show up at the harder end. Bitmask DP uses an integer's bits to represent a set, usually when n is small (around 15 to 20) because the state count is 2^n.

Second gotcha: space optimization.

• Many 2D DPs only ever read the previous row.
• You can drop from O(m * n) to one or two rows of O(n).
• Mention this out loud even if you do not implement it. It is a cheap senior signal that costs you one sentence.

6Complexity#

The rule is clean and worth memorizing cold.

• Time = (number of states) times (work per state).
• Space = number of states, before any optimization.

Applied to the families above:

• Coin Change with amount A and k coins: A states, k work each, so O(A * k) time and O(A) space.
• A 2D string DP of lengths m and n: O(m * n) states, O(1) work each in simple cases, so O(m * n) time and space. Drop to O(min(m, n)) space if you only keep one row.
• Bitmask DP over n items: 2^n subsets times n work gives O(2^n * n). That is exactly why n stays around 15 to 20; at n = 20 that is already about 20 million operations.

Say it this way out loud and you sound like you have done this a hundred times, because the formula really is just states times work: state the recurrence, count the cells, count the work per cell, multiply. Done.

7Mistakes that cost people the round#

I have watched strong engineers lose DP rounds. It is almost never because they could not code. It is these.

• Fuzzy state definition. They write dp[i] and never say in words what it means. The recurrence drifts, the base case does not match, nothing lines up. Write the sentence first. Always.
• Jumping straight to a table. They try to fill a 2D array before they understand the recurrence, get lost in indices, and panic around minute 20. Start with the recursive relation in plain English, then add the memo.
• Wrong base cases. The recurrence is perfect but dp[0] is set wrong, so every value is off by a constant. Hand-check the two smallest inputs against reality before you trust the whole table.
• Off-by-one in the answer cell. They compute the whole table correctly and then return dp[n-1] when the answer is dp[n], or the last cell when the answer is the max over all cells (classic in LIS). Know exactly which cell holds the result before you write the return.
• Not noticing the overlap. They write clean recursion, forget the memo, and submit an exponential solution thinking it is DP. No cache, no DP. The interviewer asks for complexity and the whole thing unravels.
• Silence. They solve it in their head and fill a table with zero narration. The interviewer cannot follow, cannot tell if you are stuck or thinking, and cannot hand you the hint that would save the round. Talk through state and recurrence as you go.

The meta-mistake: treating DP as pattern-matching to memorized problems.

• The ones who pass reason from the state up, so a prompt they have never seen is still tractable.
• Build that habit in practice and the loop stops being a dice roll.

8Your practice path (named problems by difficulty)#

Do them in this order. Each tier builds the reflex for the next. Do not jump ahead, even if the hard list looks more interesting.

Foundations (build the reflex):

• Climbing Stairs
• House Robber
• Min Cost Climbing Stairs
• Maximum Subarray (Kadane's, the gateway DP)

1D and counting:

• Coin Change
• Coin Change II (counting ways, and notice how the loop order differs from the min-coins version)
• Word Break
• Decode Ways

2D grids and strings:

• Unique Paths
• Minimum Path Sum
• Longest Common Subsequence
• Edit Distance

Subsequence and knapsack:

• Longest Increasing Subsequence
• Partition Equal Subset Sum
• Target Sum
• Longest Palindromic Subsequence

Hard, for the senior loop:

• Best Time to Buy and Sell Stock III / IV
• Burst Balloons
• Regular Expression Matching
• Palindrome Partitioning II

Spend real time on the first two tiers, even 15 to 20 problems before moving up.

• Most people rush them, never build the reflex, and then drown in Burst Balloons wondering why.
• The reflex is the asset; the hard problems only test whether you have it.

9Where this shows up (which companies and rounds)#

DP is a staple of the algorithm rounds at the big product companies.

• Google, Meta, Amazon, and Microsoft all lean on it, especially the string and grid variants (edit distance, LCS, unique paths) for mid-to-senior levels.
• Trading firms and quant shops push the harder interval and bitmask flavors, often with a tight runtime budget.
• Startups vary, but a clean DP answer always reads as a senior signal because it shows you can turn a vague optimization prompt into a precise recurrence.

When and where it lands in the loop.

• It tends to appear in the dedicated coding round rather than system design.
• More often as the second or "stretch" problem once you have shown you can handle a warm-up.
• Expect the interviewer to twist a known problem (add a constraint, change "min" to "count the ways") specifically to see whether you memorized or actually understand the state.

Want to see which DP flavors specific companies favor and how they phrase them? Check the company guides to map this pattern to the loops you are actually facing.