Classic 1D DP

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 1 Time to complete: ~30 minutes

What Makes a Problem "1D DP"
Climbing Stairs — Naive Recursion
Climbing Stairs — DP Solution
House Robber — Naive Recursion
House Robber — DP Solution
Recognizing the 1D DP Pattern
Summary & Next Steps

1. What Makes a Problem "1D DP"

A problem is "1D DP" when the state you need to remember at each step can be described with a single index — usually "the answer up to position i." Both problems in this chapter fit that shape: the answer for position i depends only on the answers at a small number of earlier positions.

2. Climbing Stairs — Naive Recursion

Problem: You're climbing a staircase with n steps. Each move you can climb 1 or 2 steps. How many distinct ways can you reach the top?

def climb_stairs_naive(n):
    if n <= 2:
        return n
    return climb_stairs_naive(n - 1) + climb_stairs_naive(n - 2)
    # Ways to reach step n = ways to reach (n-1) + ways to reach (n-2)
    # — this is structurally identical to Fibonacci, and just as exponential

Following Chapter 1's recipe: this recurses into overlapping subproblems (reaching step 5 is needed by both the path through step 6 and step 7), and the recursion tree looks exactly like Fibonacci's from Chapter 1 — same O(2ⁿ) blowup.

3. Climbing Stairs — DP Solution

Applying tabulation directly (following Chapter 1, Section 5):

def climb_stairs(n):
    if n <= 2:
        return n
 
    prev2, prev1 = 1, 2      # ways to reach step 1, step 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
    # O(n) time, O(1) space

4. House Robber — Naive Recursion

Problem: You're robbing houses along a street, represented as a list of amounts of money. You cannot rob two adjacent houses (an alarm triggers). Maximize the total amount robbed.

def rob_naive(houses, i=0):
    if i >= len(houses):
        return 0
 
    skip = rob_naive(houses, i + 1)                      # don't rob house i
    take = houses[i] + rob_naive(houses, i + 2)          # rob house i, skip i+1
    return max(skip, take)
    # At each house: two recursive branches → O(2ⁿ) again

The recursive relationship: the best result starting at house i is the better of (a) skip this house or (b) rob this house and skip the next one. This is optimal substructure — but the same subproblems (rob_naive(houses, i) for various i) get recomputed across different branches, so it's a DP candidate.

5. House Robber — DP Solution

Working bottom-up, left to right, where best_through[i] means "the max amount robbable using houses 0..i":

def rob(houses):
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
 
    prev2, prev1 = 0, houses[0]     # best_through[-1], best_through[0]
    for i in range(1, len(houses)):
        current = max(prev1, prev2 + houses[i])
        prev2, prev1 = prev1, current
    return prev1
    # O(n) time, O(1) space

Trace through houses = [2, 7, 9, 3, 1]:

i=0: prev2=0,  prev1=2                 (best using just house 0)
i=1: current = max(2, 0+7)  = 7        prev2=2,  prev1=7
i=2: current = max(7, 2+9)  = 11       prev2=7,  prev1=11
i=3: current = max(11, 7+3) = 11       prev2=11, prev1=11
i=4: current = max(11, 11+1)= 12       prev2=11, prev1=12
Result: 12   (rob houses at index 0, 2, 4 → 2 + 9 + 1 = 12)

6. Recognizing the 1D DP Pattern

Both problems share a signal worth memorizing for Module 11's pattern cheat sheet: "the best answer up to position i depends only on the best answer(s) at i-1 and/or i-2." Whenever a problem description involves counting paths, ways, or maximizing/minimizing a value over a sequence where each choice depends on a fixed, small window of previous choices, 1D DP with two rolling variables (as in Sections 3 and 5) is usually the target shape — not a growing array, unless you specifically need to look back further than a constant window.

7. Summary & Next Steps

Key Takeaways

Climbing Stairs and House Robber both reduce to Fibonacci-shaped recurrences — a strong hint that "counting ways" or "adjacent-constraint optimization" problems are 1D DP candidates.
The DP solution for both drops from O(2ⁿ) naive recursion to O(n) time, O(1) space once you notice only the last one or two states matter.
The general shape — two rolling variables updated in a single left-to-right pass — is worth recognizing on sight, since it reappears constantly in interview problems.

Concept Check

Why is House Robber's naive recursive solution O(2ⁿ), structurally similar to Fibonacci?
In the House Robber trace, why does current = max(prev1, prev2 + houses[i]) correctly represent "skip vs. take" at each house?
What's the signal that a 1D DP solution can be compressed to O(1) space instead of keeping a full table?

Next Chapter

→ Chapter 3: Classic 2D DP

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index