LeetCode Solutions← Back to Patterns
Dynamic ProgrammingMedium
1D DP
Store answers to overlapping subproblems in a 1D array, building bottom-up.
How it works
One-dimensional Dynamic Programming stores the solution to each subproblem in a single array, typically indexed by position or amount. The recurrence relation dp[i] = f(dp[i-1], dp[i-2], ...) tells you how to compute the next state from previous ones. You fill the array from smaller subproblems to larger ones (bottom-up), ensuring each value is already computed when needed. Classic 1D DP problems include Fibonacci / Climbing Stairs (dp[i] = dp[i-1] + dp[i-2]), Coin Change (dp[amount] = min coins), and House Robber (dp[i] = max(dp[i-1], dp[i-2] + nums[i])). When dp[i] depends on only a few previous values, you can optimize space from O(n) to O(1) by keeping only those values.
Interactive Playground
dp[0]=1, dp[1]=1. Fibonacci — 1 way to reach step 0 or 1.
Speed
When to use
- Fibonacci-style recurrences
- Climbing stairs, coin change, house robber
- Longest increasing subsequence
✅Tips
1Start by writing the top-down recursive solution with memoization, then convert to bottom-up iteratively.
2Define dp[i] clearly — what does it represent? "Minimum cost to reach step i" or "maximum profit at day i".
3When dp[i] depends on dp[i-1] and dp[i-2] only, replace the array with two variables (prev1, prev2).
4For "can we reach the end?" problems, initialize dp[0] = true and propagate reachability forward.
❌Common Mistakes
!Wrong initialization — dp[0] and dp[1] base cases are often the trickiest part.
!Incorrect recurrence — off by one in the index or wrong direction (forward vs backward).
!Accessing dp[i-1] when i=0 without bounds checking — guard with `if i > 0` or initialize correctly.
!Confusing "minimum" and "maximum" — initializing min-dp with 0 instead of Infinity.
💡 Key Insight:dp[i] depends only on dp[i-1] (or a few previous states) — often O(1) space.