Dynamic programming
Define the state, write the recurrence, fix the base case and fill the table in an order where every dependency is ready.
Coin Change. Given coin denominations coins (unlimited supply) and an amount, return the fewest coins that make the amount, or -1 if it cannot be made.
Signals that point here
- "Minimum / maximum / number of ways" over choices that build on smaller versions of the same problem.
- A brute-force recursion that recomputes the same arguments (overlapping subproblems).
- Sequences and strings: edit distance, longest common subsequence, longest increasing subsequence, house robber, knapsack.
The idea
Say four things before coding. State: dp[a] is the fewest coins for amount a. Recurrence: dp[a] = 1 + min(dp[a - c]) over coins c <= a. Base: dp[0] = 0. Order: increasing a, because dp[a] reads only smaller amounts.
Start top-down (recursion plus memo) if that is how you think, then convert to bottom-up if asked about stack depth or constant factors. Both are the same algorithm. Greedy (largest coin first) is wrong for coins like [1, 3, 4] and amount 6; giving that counter-example is a strong signal.
def coin_change(coins: list[int], amount: int) -> int:
impossible = amount + 1 # more coins than could ever be needed
dp = [0] + [impossible] * amount # dp[a] = fewest coins for a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] <= amount else -1public static class DynamicProgramming
{
public static int CoinChange(int[] coins, int amount)
{
int impossible = amount + 1; // more coins than could ever be needed
var dp = new int[amount + 1]; // dp[a] = fewest coins for a
Array.Fill(dp, impossible);
dp[0] = 0;
for (int a = 1; a <= amount; a++)
foreach (int c in coins)
if (c <= a) dp[a] = Math.Min(dp[a], dp[a - c] + 1);
return dp[amount] <= amount ? dp[amount] : -1;
}
}Complexity
O(amount · len(coins)) time, O(amount) space.
Pitfalls interviewers watch for
- Using
float('inf')and then returning it, orint.MaxValueand overflowing on+ 1in C#. - Getting the loop order wrong for counting problems: coins outer counts combinations, amounts outer counts permutations.
- Jumping to a table without stating the state in words. Interviewers grade the definition.
Variants worth knowing
- Coin Change II (number of ways):
ways[a] += ways[a - c]with coins in the outer loop. - 0/1 knapsack: iterate capacity downward so each item is used once.
- Longest common subsequence: a 2D table where
dp[i][j]depends oni-1andj-1.
Test it like the interviewer will
coin_change([1, 2, 5], 11)returns3coin_change([2], 3)returns-1coin_change([1], 0)returns0coin_change([1, 3, 4], 6)returns2- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: coin_change([1, 3, 4], 6)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Count the number of ways to climb
nstairs taking 1 or 2 steps. - Return the edit distance between two strings.
- Return the length of the longest increasing subsequence in
O(n log n).
Check yourself
What four things should you state before coding a DP?
State, recurrence, base case, evaluation order.
Give a coin set where greedy fails.
[1, 3, 4] with amount 6: greedy gives 4+1+1 (3 coins), DP gives 3+3 (2 coins).