1-D Dynamic Programming

What you'll learn

Most DP problems reduce to a handful of shapes. The simplest is 1-D DP, where the state is a single index into an array. Drill these patterns — coin change, house robber, rod cutting — and you'll spot them everywhere.

By the end you'll be able to:

• Fill a 1-D DP table with multiple dependencies
• Recognize the "take it or leave it" recurrence
• Space-optimize a 1-D DP to a few variables

Coin change

Given coin denominations and a target amount, find the fewest coins that sum to it. The state dp[a] is the fewest coins for amount a; each coin c offers a path from dp[a - c]. Watch it build up, trying every coin for each amount:

In code

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount        # dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

House robber

Houses in a row each hold some loot, but you can't rob two adjacent houses. The recurrence is the classic "take it or leave it": dp[i] = max(dp[i-1], dp[i-2] + loot[i]) — either skip house i, or rob it and add the best from two houses back:

def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        # best if we skip x vs. rob x (plus best before last)
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Rod cutting

A rod of length n can be cut into pieces, each length with a price. Maximize the total. The state dp[len] is the best revenue for a rod of that length, and the transition tries every first cut: dp[len] = max over k of (price[k] + dp[len - k]). It's the same "try every option" shape as coin change, maximizing instead of minimizing.

Recap & quick check

When the state needs two indices, we move to a 2-D table — starting with the famous knapsack. Next up: Module 17 — Knapsack & Subset-Sum DP.