Dynamic programming
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
When it applies
Dynamic programming is for problems with overlapping subproblems and an optimal substructure: the best answer for a state is built from the best answers of smaller states. Always write the recursion first and only then decide between memoising it and filling a table bottom-up.
Signals: "fewest", "number of ways", "maximum value subject to", and any brute force whose recursion tree visibly repeats arguments.
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
best = [BASE] + [SENTINEL] * n
for state in range(1, n + 1):
for move in moves(state):
prev = state - move
if prev >= 0:
best[state] = min(best[state], best[prev] + cost(move))
return best[n]std::vector<int> best(n + 1, SENTINEL);
best[0] = BASE;
for (int state = 1; state <= n; ++state)
for (int move : moves(state))
if (state - move >= 0)
best[state] = std::min(best[state], best[state - move] + cost(move));
return best[n];int[] best = new int[n + 1];
java.util.Arrays.fill(best, SENTINEL);
best[0] = BASE;
for (int state = 1; state <= n; state++)
for (int move : moves(state))
if (state - move >= 0)
best[state] = Math.min(best[state], best[state - move] + cost(move));
return best[n];const best = new Array(n + 1).fill(SENTINEL);
best[0] = BASE;
for (let state = 1; state <= n; state++)
for (const move of moves(state))
if (state - move >= 0)
best[state] = Math.min(best[state], best[state - move] + cost(move));
return best[n];let mut best = vec![SENTINEL; n + 1];
best[0] = BASE;
for state in 1..=n {
for &mv in moves(state) {
if state >= mv {
best[state] = best[state].min(best[state - mv] + cost(mv));
}
}
}
best[n]-- A lazy array is the table; each entry may refer to earlier ones.
best = listArray (0, n) [f s | s <- [0 .. n]]
where f 0 = base
f s = minimum [best ! (s - m) + cost m | m <- moves s, m <= s]Problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Easy10 minOne trade: the best profit
Buy on one day and sell on a later day. The best profit from selling today is today's price minus the lowest price so far.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Medium15 minLongest common block
Return the length of the longest contiguous block that appears in both lists. The table holds the best block ending at each pair of positions.
Open the problem → Medium15 minLongest common subsequence
Return the length of the longest subsequence that two strings share: a table over pairs of prefixes.
Open the problem → Medium15 minLongest increasing subsequence
Return the length of the longest strictly increasing subsequence, with the classic O(n²) table: the best subsequence ending at each position.
Open the problem → Medium15 minOrdered ways to reach a total
Count the ordered sequences of numbers, each usable any number of times, that sum to a target. The same loops as coin change, swapped.
Open the problem → Medium15 minThe cheapest path through a grid
Move only right or down from the top-left cell to the bottom-right one, paying each cell's cost. Each cell's cheapest arrival comes from above or the left.
Open the problem → Medium15 minThe largest-sum subarray
Return the largest sum of a non-empty contiguous subarray: the best sum ending at each position, extend or restart.
Open the problem → Medium15 minThe unbounded knapsack
Every item can be taken as many times as you like. One array, capacities upwards, so an item can follow itself.
Open the problem → Medium15 minWays to make an amount
Count the combinations of coins (unlimited of each) that add up to an amount. Coins on the outer loop, so each combination is counted once.
Open the problem → Medium20 minFewest coins to make an amount
Greedy fails, recursion repeats itself, and one array fixes both. The cleanest first dynamic programme.
Open the problem → Medium20 minLongest palindromic subsequence
Return the length of the longest subsequence of a string that reads the same forwards and backwards: an interval table filled by length.
Open the problem → Medium20 minLongest palindromic substring
Return the longest contiguous palindrome in a string, the earliest one on ties. Expand from each of the 2n − 1 centres.
Open the problem → Medium20 minThe 0/1 knapsack
Choose items, each at most once, to maximise total value without exceeding the capacity. One array, filled downwards per item.
Open the problem → Medium20 minThe bounded knapsack
Each item comes in a limited number of copies. Split the copies into bundles of 1, 2, 4, … and solve a 0/1 knapsack over the bundles.
Open the problem → Medium20 minThe fewest coins from a limited supply
Pay an amount with the fewest coins when you hold only so many of each. Binary-split the supply into bundles and run a 0/1 knapsack with min.
Open the problem → Medium20 minThe largest chain of divisors
Find the size of the largest subset of distinct positive integers in which every pair divides one way or the other. Sort first, and divisibility becomes a chain.
Open the problem → Medium15 minCan you reach the last position?
nums[i] is the furthest jump from position i. Can you get from the first position to the last? A reachability DP that collapses to one variable.
Open the problem → Medium15 minPaths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Medium15 minSplit an integer for the largest product
Write n as a sum of at least two positive integers and maximise their product. Parts can repeat: an unbounded knapsack over part sizes.
Open the problem → Medium15 minSplit into two equal halves
Can the numbers be divided into two groups with the same sum? Only if half the total is reachable by some subset.
Open the problem → Medium20 minDice rolls with a target sum
Roll n dice with k faces each. In how many ways can the faces add up to the target? Exactly n picks, so the number of dice used is part of the state.
Open the problem → Medium20 minWays to pay with a limited supply
Count the combinations of coins, each available a limited number of times, that pay an amount. Binary splitting would overcount here, so use a sliding window sum.
Open the problem → Medium25 minHow many longest increasing subsequences
Count the strictly increasing subsequences of maximum length. Keep, for each position, the best length ending there and how many subsequences achieve it.
Open the problem → Medium25 minIs a string an interleaving of two others?
Decide whether s3 can be built by merging s1 and s2, each kept in order. The state is how much of each has been used.
Open the problem → Medium25 minLongest increasing subsequence in O(n log n)
Keep, for each length, the smallest value an increasing subsequence of that length can end on; binary search does the rest.
Open the problem → Medium15 minCut a rod for the most money
A piece of length L sells for prices[L − 1]. Cut a rod of length n to maximise revenue: the best first piece plus the best for what remains.
Open the problem → Medium15 minLargest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Medium15 minSubsets with a given sum
Count the subsets of a list (by position) that add up to the target. The 0/1 knapsack with sum: totals downwards, each element at most once.
Open the problem → Medium20 minCan the first player win?
Players alternately take a number from either end of a row. With both playing perfectly, does the first player finish with at least as much?
Open the problem → Medium20 minThe largest product of a subarray
Return the largest product of a non-empty contiguous subarray. A negative number swaps the best and the worst, so keep both.
Open the problem → Medium20 minThe largest square of ones
Find the area of the largest all-ones square in a 0/1 grid. The square ending at a cell is limited by the three squares ending next to it.
Open the problem → Medium20 minThe longest rise-then-fall subsequence
Return the length of the longest subsequence that strictly increases and then strictly decreases. Run the increasing table from both ends and join them at the peak.
Open the problem → Medium20 minThe smallest difference between two groups
Divide numbers into two groups so the sums are as close as possible. Find the reachable subset sum nearest to half the total.
Open the problem → Medium20 minThe largest sum on a circle
The list wraps around. The best stretch either does not wrap (ordinary Kadane) or does, and then it is the total minus the worst stretch.
Open the problem → Medium20 minThe longest alternating subsequence
Return the length of the longest subsequence whose successive differences alternate between positive and negative. Two numbers carry the whole table.
Open the problem → Medium20 minThe shortest common supersequence
The shortest string that contains both strings as subsequences. Every shared character can be written once: n + m − LCS.
Open the problem → Medium20 minWays to decode a string of digits
Letters are encoded as 1 to 26. Count the ways to read a string of digits back as letters: one digit or two at a time, with zeros as the trap.
Open the problem → Hard25 minHow many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Hard25 minThe cheapest order to multiply matrices
Matrix i is dims[i] × dims[i + 1]. Return the fewest scalar multiplications needed to compute the whole product.
Open the problem → Hard25 minThe fewest cuts into palindromes
Cut a string into pieces that are all palindromes, using as few cuts as possible. A palindrome table, then a DP over prefixes.
Open the problem → Hard30 minBurst balloons for the most coins
Bursting a balloon earns the product of it and its current neighbours. Choosing which balloon goes last in each range makes the two sides independent.
Open the problem → Hard20 minThe fewest insertions to make a palindrome
Insert characters anywhere to make a string read the same backwards. Matching ends are free; otherwise insert a copy of one end and shrink the interval.
Open the problem → Hard30 minEdit distance between two strings
The cost of turning one string into another, built from the costs of turning their prefixes into each other.
Open the problem → Hard30 minThe cheapest way to cut a stick
Each cut costs the length of the piece being cut. Choose the order of cuts to minimise the total: an interval DP over the sorted cut positions.
Open the problem → Hard30 minWildcard pattern matching
In the pattern, ? matches one character and * matches any run, including none. Does the pattern match the whole string?
Open the problem → Hard30 minThe least starting health
Cross a grid of gains and losses, right or down, without health ever dropping to zero. The requirement at a cell depends on what comes after, so fill from the end.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.