1D and Linear DP¶

Phase 4 | Weeks 24–25

1D DP is where the pattern becomes physical. Every problem here has a single sequence (array, amount, index), and dp[i] represents the best answer for the first i elements, or the answer for a specific index, or the number of ways to reach a state. The transitions are short. The insights are not.

Work through every derivation below from scratch. Don’t skip the Fibonacci derivation just because it’s “easy” — it demonstrates the exact reasoning pattern you’ll apply to every problem after it.

Fibonacci: The Full Derivation¶

Problem: Compute fib(n) where fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).

Step 1: Naive recursion — O(2^n)¶

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

Subproblems overlap heavily. fib(3) is computed twice when computing fib(5).

Step 2: Memoization — O(n) time, O(n) space¶

memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Step 3: Tabulation — O(n) time, O(n) space¶

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Step 4: Space-optimized — O(n) time, O(1) space¶

The recurrence only needs the last two values. No need to keep the full table.

if n == 0: return 0
a, b = 0, 1
for _ in range(2, n + 1):
    a, b = b, a + b
return b

Climbing Stairs¶

Problem: You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

5 Questions:

State: dp[i] = number of ways to reach step i
Transition: To reach step i, you came from step i-1 (1 step) or step i-2 (2 steps). dp[i] = dp[i-1] + dp[i-2]
Base cases: dp[0] = 1 (one way to stand at ground), dp[1] = 1
Answer: dp[n]
Space opt: Yes — same as Fibonacci, only last two values needed

This is structurally identical to Fibonacci. That’s the point. Pattern recognition is the skill.

House Robber¶

Problem: Rob houses in a line. Can’t rob two adjacent houses. Maximize total.

5 Questions:

State: dp[i] = maximum money robbing from houses 0..i
Transition: For house i, either rob it (skip i-1, take dp[i-2] + nums[i]) or don’t (take dp[i-1]) dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
Answer: dp[n-1]
Space opt: Yes — only two previous values needed

if len(nums) == 1: return nums[0]
a, b = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
    a, b = b, max(b, a + nums[i])
return b

House Robber II (Circular Array)¶

Problem: Same as House Robber, but the houses form a circle. House 0 and house n-1 are adjacent.

The circular constraint: You can’t rob both the first and last house. So: run the 1D House Robber twice — once on nums[0..n-2] (exclude last), once on nums[1..n-1] (exclude first). Take the max of both results.

def rob_linear(nums):
    a, b = 0, 0
    for num in nums:
        a, b = b, max(b, a + num)
    return b

return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

This trick — decomposing a circular constraint into two linear subproblems — appears in other problems too. Recognize it.

Coin Change (Minimum Coins)¶

Problem: Given coin denominations and a target amount, find the minimum number of coins to make the amount. Return -1 if impossible.

5 Questions:

State: dp[i] = minimum coins to make amount i
Transition: For each coin c, if i >= c and dp[i-c] != -1: dp[i] = min(dp[i], dp[i-c] + 1)
Base cases: dp[0] = 0 (zero coins to make amount 0)
Answer: dp[amount] if not infinity, else -1
Space opt: No — need the entire table

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
    for coin in coins:
        if i >= coin and dp[i - coin] != float('inf'):
            dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

Note: This is unbounded knapsack — coins can be used multiple times. Inner loop iterates amounts (states), outer loop iterates items. See the Knapsack file for why this matters.

Coin Change II (Number of Ways)¶

Problem: Same coins, same target. Count the number of ways to make the amount (order doesn’t matter).

State: dp[i] = number of ways to make amount i. Base case: dp[0] = 1 (one way to make 0: use no coins). Transition: For each coin c, dp[i] += dp[i - c]

Critical difference from Coin Change I: The outer loop is over coins, inner loop over amounts. This avoids counting permutations (e.g., {1,2} and {2,1} as different ways).

dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:           # outer loop: coins
    for i in range(coin, amount + 1):  # inner loop: amounts
        dp[i] += dp[i - coin]
return dp[amount]

If you swap the loops, you count ordered sequences (permutations), not combinations. The loop order determines the semantics.

Jump Game I (Can You Reach the End?)¶

Problem: Each element tells you the max jumps you can make from that index. Can you reach the last index?

Greedy is better here but the DP version is instructive:

dp[i] = True if you can reach index i.

dp = [False] * len(nums)
dp[0] = True
for i in range(1, len(nums)):
    for j in range(i):
        if dp[j] and j + nums[j] >= i:
            dp[i] = True
            break
return dp[-1]

The greedy O(n) solution: track the farthest index reachable so far.

farthest = 0
for i, jump in enumerate(nums):
    if i > farthest: return False
    farthest = max(farthest, i + jump)
return True

Lesson: When a greedy solution exists and is provably correct, use it. DP is not always the answer.

Jump Game II (Minimum Jumps)¶

Problem: Same setup. Minimum number of jumps to reach the last index.

DP: dp[i] = minimum jumps to reach index i. O(n²).

Greedy (BFS-like) O(n): Track current range of reachable indices and next range.

jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
    farthest = max(farthest, i + nums[i])
    if i == current_end:
        jumps += 1
        current_end = farthest
return jumps

Pattern Recognition: When Does a Problem Fit 1D Linear DP?¶

You’re looking at a 1D linear DP problem when:

Input is a 1D sequence (array, amount, index range)
You make a decision at each step: take/skip, rob/don’t, include/exclude
The decision at step i only affects adjacent or recent steps (bounded look-back)
You want an optimal value (min/max) or a count of ways

Trigger phrases: “maximum/minimum subarray/subsequence”, “number of ways to reach”, “can you achieve X”, “choose elements that don’t violate a constraint”

Practice Problems¶

Easy¶

Medium¶

Hard¶

LeetCode 45 - Jump Game II (greedy + DP insight)

Target: Solve all 8 without looking at solutions after reading this file. If you get stuck, re-read the derivation for the closest analogous problem, then try again. Don’t look at hints first.

Navigation ← DP Foundations | Phase 4 README | Next: 2D Grid DP →