1D Dynamic Programming
The Intuition
Imagine you're standing at the bottom of a staircase with 10 steps. You can take either 1 step or 2 steps at a time. How many different ways can you reach the top? You could try to list every possible path, but that's chaos. Instead, think about it from step 10's perspective. You can only arrive at step 10 from step 9 (by taking 1 step) or from step 8 (by taking 2 steps). So the number of ways to reach step 10 equals the ways to reach step 9 plus the ways to reach step 8.
Now you need the answer for step 9. Same logic: it depends on steps 8 and 7. Step 8 depends on steps 7 and 6. You keep peeling back the layers until you hit the base cases. Step 1 has 1 way. Step 2 has 2 ways. From there, you build upward. Step 3 = step 2 + step 1 = 3. Step 4 = step 3 + step 2 = 5. Each answer snaps together from previous answers like building blocks.
That's the whole idea behind 1D DP. You define what dp[i] means ("the answer for the first i things"), figure out how dp[i] relates to smaller subproblems (the recurrence), nail down your base cases, and fill in the table from small to large. Every cell in the table gets computed exactly once, and by the time you need it, the cells it depends on are already filled in.
If dp[i] only ever looks at dp[i-1] and dp[i-2], you don't even need the full table. Two variables will do. Swap them as you go. You've just reduced your space from O(n) to O(1) while keeping the same logic. The recurrence stays the same; you're just recycling storage.
Fibonacci-style problems, climbing stairs, house robber, coin change, longest increasing subsequence, word break, decode ways, or any problem with optimal substructure along one axis.
- Problem has no overlapping subproblems (use greedy)
- State space is too large to memoize (use approximation)
- Problem requires exploring all possibilities (use backtracking)
Variations:
- Space-optimized: When dp[i] depends only on dp[i-1] and dp[i-2], use two variables instead of an array.
- Top-down (memoization): Recursive with caching; more intuitive for complex recurrences.
- Bottom-up (tabulation): Iterative; avoids recursion overhead and stack limits.
- Base case with n = 0 or n = 1
- Single element array
- No valid solution exists (return -1 or 0)
Key Points
- •Define state: dp[i] = optimal answer considering first i elements
- •Find recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
- •Identify base cases: dp[0], dp[1], etc.
- •Optimize space if dp[i] only depends on a constant number of previous states
- •Bottom-up (tabulation) avoids recursion overhead; top-down (memoization) is more intuitive
Code Template
1 def climb_stairs(n):
2 """Number of ways to climb n stairs (1 or 2 steps)."""
3 if n <= 2:
4 return n
5 prev2, prev1 = 1, 2
6 for _ in range(3, n + 1):
7 curr = prev1 + prev2
8 prev2, prev1 = prev1, curr
9 return prev1
10
11 def house_robber(nums):
12 """Maximum sum of non-adjacent elements."""
13 if not nums:
14 return 0
15 if len(nums) == 1:
16 return nums[0]
17 prev2, prev1 = 0, nums[0]
18 for i in range(1, len(nums)):
19 curr = max(prev1, prev2 + nums[i])
20 prev2, prev1 = prev1, curr
21 return prev1
22
23 def longest_increasing_subsequence(nums):
24 """Length of LIS using DP + binary search (O(n log n))."""
25 from bisect import bisect_left
26 tails = []
27 for num in nums:
28 pos = bisect_left(tails, num)
29 if pos == len(tails):
30 tails.append(num)
31 else:
32 tails[pos] = num
33 return len(tails)Common Mistakes
- Wrong base case initialization
- Off-by-one errors in the recurrence
- Not considering all transitions in the recurrence relation