- 1
The 1D DP Recipe
Four questions solve every 1D DP: define dp[i] in words, find the recurrence via the last decision, order the fill, and know where the answer lives.
Code orderMultiple choice - 2
Maximum Subarray
Kadane's algorithm is 1D DP in disguise: dp[i] = best sum ending at i = max(nums[i], dp[i-1] + nums[i]) — and the answer is the max over ALL cells, not the last one.
Complete codeDebugMultiple choiceTrace - 3
House Robber II
The street is a circle — house 0 and house n-1 are neighbors. Break the circle: run the LINEAR robber twice, once without the first house and once without the last, and take the max.
DebugMultiple choiceTrace - 4
Delete and Earn
Bucket equal values into gain[v] = v x count(v); deleting v wipes out v-1 and v+1, so the choice collapses to House Robber on the value line.
Complete codeMultiple choiceTrace - 5
Coin Change
Unbounded minimization: dp[a] = fewest coins making exactly a, the min over coins of dp[a-c] + 1 — the table beats greedy, and a surviving infinity means -1.
Complete codeMultiple choiceTrace - 6
Perfect Squares
Coin Change in disguise: the coins are 1, 4, 9, 16, ... — dp[n] = min over k*k <= n of dp[n - k*k] + 1, and greedy's biggest-square instinct loses.
Complete codeMultiple choiceTrace - 7
1D DP CheckpointCheckpoint
No new concepts — transfer the island's 1D recipes to unseen problems: turbulent runs ending at i, a max-product sweep that needs two states, a frog minimizing jump costs, and a walk over taboo positions.
Complete codeDebugMultiple choiceTrace - 8
1D DP ReviewReview
Mixed recap of the island: ending-at states and the global max sweep, reductions to robber and coin change, unbounded reuse vs take-skip, INF sentinels with the -1 read-out, circles as two linear runs, and the table-vs-tree cost contrast.
Complete codeMultiple choice - 9
Boss: Decode WaysBoss
The island's final test: count the decodings of a digit string. Every prefix adds a single-letter route and a guarded pair route — and the boss's traps are '0' standing alone and pairs like "27" or "06" that are not letters.
Complete codeDebugCode orderMultiple choiceTrace
Dynamic Programming is part of AlgoFox Pro
You can read the whole course outline here. The exercises are in the app, along with your streak, your mistake review, and the progress that carries across your devices.
Pro starts with a 3 day free trial. The app store decides who is eligible for an introductory offer, and a lapsed subscription does not get another one.
Already subscribed in the app? Sign in with the same account and Pro works here too. Quick Play and Battle are free on the web, and so is the first course in every subject.