DSA & Implementation · advanced
1D DP
Linear state recurrences.
Mental model
Dynamic programming is recursion with the repeated work cached. Define the state (what does dp[i] mean?), the recurrence (how does dp[i] build on earlier states?), and the base case. 1D DP means the state is a single index along a sequence.
How to study 1D DP
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Dynamic programming (Wikipedia), Algorithms (Erickson) — Ch. 3: Dynamic Programming, MIT 6.006 L15 — Dynamic Programming Part 1 (SRTBOT, Fib, DAGs, Bowling) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare 1D DP with 2D DP. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete House robber (1D DP), Best Time to Buy and Sell Stock, Maximum Subarray and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Common mistakes
- Starting to code before clearly defining what dp[i] represents
- Wrong iteration order so a state is read before it is computed
- Missing or wrong base cases
Learn from primary sources
Practice and explain it back
House robber (1D DP)
Given values along a line, pick a non-adjacent subset with maximum sum.
Expected evidence: rob([2,7,9,3,1]) -> 12
Open the interactive drill →Best Time to Buy and Sell Stock
LeetCode #121 — Best Time to Buy and Sell Stock. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Maximum Subarray
LeetCode #53 — Maximum Subarray. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/maximum-subarray/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Climbing Stairs
LeetCode #70 — Climbing Stairs. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/climbing-stairs/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Coin Change
LeetCode #322 — Coin Change. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/coin-change/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →House Robber
LeetCode #198 — House Robber. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/house-robber/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Jump Game
LeetCode #55 — Jump Game. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/jump-game/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Non-overlapping Intervals
LeetCode #435 — Non-overlapping Intervals. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/non-overlapping-intervals/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- The recurrence looks right but the answers are wrong. What is the first thing to check about iteration order?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.