Dynamic Programming I — 1-D

Dynamic programming scares people more than anything else — but it’s a single idea (don’t recompute) plus one skill (find the recurrence). Get those and DP becomes mechanical.

When DP applies, and the idea

DP applies when two things are true:

1. Overlapping sub-problems — the naive recursion solves the same smaller problem many times (classic Fibonacci recomputes fib(3) exponentially often).
2. Optimal substructure — the answer to the big problem is built from answers to smaller ones.

The fix is simple: solve each sub-problem once and store the result. Two styles: top-down memoisation (recursion + a cache) or bottom-up tabulation (fill a table from the base cases up). Both turn exponential recursion into O(n).

The real work — maybe 90% of a DP problem — is finding the recurrence: the formula that builds a bigger answer from smaller ones, plus the base case. Once you have it, the code is a short loop.

Worked example: climbing stairs

You can climb 1 or 2 steps at a time; how many ways to reach step n? You reach step n from step n−1 (one step) or n−2 (two steps), so ways[n] = ways[n-1] + ways[n-2] — Fibonacci:

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a
# climb_stairs(5) -> 8

Note the O(1) space: 1-D DP often only needs the last couple of values, not the whole array.

Worked example: house robber

Rob houses for max money, but you can’t rob two adjacent ones. At each house: either skip it (keep dp[i-1]) or rob it (dp[i-2] + nums[i]) — take the max:

def rob(nums):
    prev, cur = 0, 0           # dp[i-2], dp[i-1]
    for n in nums:
        prev, cur = cur, max(cur, prev + n)
    return cur
# rob([2,7,9,3,1]) -> 12  (2 + 9 + 1)

Worked example: coin change

Fewest coins to make amount. dp[a] = min coins for amount a; try each coin and take the best: dp[a] = min(dp[a - coin] + 1):

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]
# coin_change([1,2,5], 11) -> 3  (5 + 5 + 1)

Worked example: longest increasing subsequence

dp[i] = length of the LIS ending at i. The O(n²) DP is dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]); a slicker O(n log n) version uses binary search (Lesson 10) on a “tails” array:

import bisect
def lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails): tails.append(x)      # extend
        else:               tails[i] = x         # replace to keep tails small
    return len(tails)
# lis([10,9,2,5,3,7,101,18]) -> 4  ([2,3,7,101])

How to approach any DP problem

1. Define the state. What does dp[i] mean? (e.g. “max money robbing houses 0..i”.) Getting the definition right is most of the battle.
2. Find the recurrence. How is dp[i] built from smaller states? (rob vs skip; try each coin; take or not take.)
3. Base case(s). dp[0], empty input.
4. Order & direction. Bottom-up loop (or memoised recursion).
5. Optimise space if only the last few states are needed.

Step-by-step walkthrough

Trace House Robber on [2, 7, 9, 3, 1]. At each house the best total is max(skip this house, rob it + best two houses back). We only need the last two answers, so two variables replace the whole table.

The answer is 12 (rob houses 0, 2 and 4: 2 + 9 + 1). Each state is computed once from smaller ones — that’s the whole idea of DP, and it turns an exponential search into O(n).

When to reach for it

Signals: “count the number of ways”, “min/max cost/value”, “can you reach / is it possible”, “longest/shortest” — where a greedy choice fails because the best choice now depends on earlier choices, and you’re making a sequence of decisions. If brute-force recursion would recompute sub-problems, it’s DP.

Pitfalls

• Vague state definition. If you can’t say precisely what dp[i] means, you can’t find the recurrence. Nail the definition first.
• Wrong base case or loop order. You must compute smaller states before the ones that depend on them.
• Reaching for DP when greedy works. Some problems have a greedy optimum (and DP is overkill); some look greedy but aren’t (coin change with odd denominations). Test small cases.

Recap

DP = overlapping sub-problems + optimal substructure, solved by storing each sub-answer once (memoise or tabulate). The skill is the recurrence: define the state precisely, express dp[i] from smaller states, set the base case. 1-D examples: climbing stairs (Fibonacci), house robber (rob vs skip), coin change (min over coins), LIS. Signal: count ways / min-max / can-reach / longest where choices depend on earlier ones.

Practice: 13 solved problems on 1-D dynamic programming → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 18 — Dynamic Programming II (2-D), the final pattern.