1-D DP¶
Also known as: Linear DP, Bottom-Up DP, One-Dimensional Memoization
The answer at position i depends only on a few earlier answers. Store those, and the exponential recursion collapses into a single left-to-right pass over an array. That's the entire idea; everything else in DP is a variation on what you store.
Before you start¶
What 'solved properly' looks like
Target: O(n) time, O(n) space — often compressible to O(1). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You identify that the answer at step i depends on answers at i-1 and i-2 (or some small set of previous steps), then you compute from left to right, storing each answer in an array as you go. Since every step reads from memory rather than recomputing, the exponential recursion becomes linear. The next insight: if you only ever need the last two values, you can drop the array and keep two variables.
Why it matters: This is the stage that most returning developers report having lost completely after relying on AI. It's also the one where the "recursion that recomputes itself" wound from the recursion fundamentals stage finally gets healed. Making the transition from "I understand recursion" to "I can spot overlapping subproblems" is the core skill.
When to reach for it¶
Reach for it when the problem asks "how many ways", "minimum/maximum cost to reach", or involves a decision at each step that depends on earlier decisions. Also when a naive recursive solution visibly recomputes the same values over and over.
When not to use it
Not every recursive problem needs DP — only ones where subproblems overlap. If they don't overlap, you're just adding a useless table. Greedy is sometimes correct and far simpler, but only when the greedy-choice property genuinely holds — prove it rather than hoping. And once it works, always ask whether you can drop the array and keep two variables.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Climbing Stairs | LeetCode | Easy | 15 mins | teaching |
| 2 | Min Cost Climbing Stairs | LeetCode | Easy | 15 mins | teaching |
| 3 | House Robber | LeetCode | Medium | 20 mins | consolidation |
| 4 | Maximum Subarray | LeetCode | Medium | 20 mins | consolidation |
| 5 | Decode Ways | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Decode Ways cleanly in one sitting — handling the two-digit decoding logic and the DP recurrence — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.