1-D Dynamic Programming

When DP applies

Two signs: overlapping subproblems (the same smaller problem recurs) and optimal substructure (the answer is built from subproblem answers). DP just caches those answers so each is computed once. If choices are independent and a local rule suffices, it’s greedy; if choices interact and recur, it’s DP.

The method (say it out loud)

1. Define the state in words — “dp[i] = the best answer considering the first i items / up to amount i.”
2. Write the transition — how dp[i] builds from earlier states (the recurrence).
3. Base cases — the smallest states.
4. Order — top-down memo (natural) or bottom-up table (iterative).
5. Optimize space — keep only the states you still read.

Top-down (memoization)

Write the recurrence, then cache it — least error-prone for tricky transitions:

from functools import cache
def coin_change(coins, amount):
    @cache
    def fewest(rem):
        if rem == 0: return 0
        if rem < 0:  return float("inf")
        return min(fewest(rem - c) + 1 for c in coins)
    ans = fewest(amount)
    return ans if ans != float("inf") else -1

Bottom-up (tabulation) + rolling state

Fill from the base cases. Often you only need the last one or two states → O(1) space:

def rob(nums):
    prev = cur = 0                  # best up to the previous / current house
    for x in nums:
        prev, cur = cur, max(cur, prev + x)   # skip x, or take x + best two back
    return cur

Top-down vs bottom-up are equivalent; bottom-up avoids recursion limits and enables rolling-array space optimization.

The recurring families

• Decisions along a line — Climbing Stairs, House Robber (take/skip), Min Cost Climbing.
• Unbounded knapsack — Coin Change (fewest coins), Coin Change II (count ways) — dp[amount], loop coins; order of loops decides combinations vs permutations.
• 0/1 knapsack (1-D rolled) — Partition Equal Subset Sum, Target Sum — iterate the capacity backwards so each item is used once.
• Subsequence on one array — Longest Increasing Subsequence (O(n²) DP, or O(n log n) with patience/binary search), Maximum Product Subarray (track min and max).
• Partition / parsing a string — Word Break (dp[i] = is prefix i segmentable), Decode Ways.
• Best contiguous — Kadane (a 1-state DP).

Worked transition: Longest Increasing Subsequence

def length_of_lis(nums):           # O(n^2) DP form
    dp = [1] * len(nums)           # dp[i] = LIS ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

(The O(n log n) version keeps the smallest tail per length via binary search — name it as the optimal.)

Pitfalls

• Wrong state definition — most DP bugs are a fuzzy dp[i]; pin it precisely in words first.
• Knapsack loop order — backward for 0/1 (reuse-once), forward for unbounded; coins-outer counts combinations, amount-outer counts permutations.
• Base cases / unreachable states — use sentinels (inf/-inf) and check them at the end.
• Recursion depth (top-down) on large n → switch to bottom-up.

Choosing in an interview

State dp[i] in words, write the recurrence, pick memo or table, then collapse space. If the subproblem needs two indices (a grid, two sequences), it’s 2-D DP — see that primer.