1-D Dynamic Programming

Dynamic programming is not a data structure or a traversal order — it's a discipline: notice that a brute-force recursive solution keeps solving the exact same smaller subproblem over and over, then remember the answer the first time instead of re-deriving it. Everything else in this topic (which array index to use as the table, what order to fill it in) is detail in service of that one idea.

From exponential recursion to a table

Climbing Stairs is the cleanest possible version of this. The natural recursive definition — ways(n) = ways(n-1) + ways(n-2) — is correct and also catastrophic: computing ways(n-1) recomputes ways(n-2) from scratch, which the outer call is also about to compute directly. That duplication compounds every level down, and ways(40) alone makes on the order of 2^40 calls. The fix isn't a smarter recursion — it's building the answer bottom-up in a table (or, when only the last one or two entries are ever needed, in a couple of rolling variables), so each subproblem gets computed exactly once.

Take it or skip it: House Robber's shape

House Robber is the shape behind more problems than its premise suggests: at each position, you make one binary choice — skip it and carry forward the best total so far, or take it and add its value to the best total from *two* steps back (since taking it forbids its neighbor). That single recurrence, best(i) = max(best(i-1), best(i-2) + nums[i]), is the same "take or skip" shape that shows up again in Partition Equal Subset Sum, just with "adjacent" replaced by "already used." House Robber II's circular twist doesn't need new machinery at all — it needs the *insight* that a circular constraint just means solving the linear version twice (excluding one end each time) and taking the better answer.

Unbounded reuse: Coin Change's shape

Coin Change and Perfect Squares share a different shape: at each amount, try *every* choice (every coin, every perfect square) and reuse is unlimited, so the recursive step reaches into dp[amount - choice] for every choice available — not just the immediately preceding index. Coin Change II adds one more subtlety on top: whether you're counting *combinations* (order doesn't matter) or *sequences* (order matters) is entirely determined by which loop is on the outside — coins outer, amount inner, counts each combination once; swap them and you're counting permutations instead, a completely different (larger) number for the exact same recurrence.

// Coin outer, amount inner: counts COMBINATIONS (order doesn't matter)
for (int coin : coins)
    for (int a = coin; a <= amount; ++a)
        dp[a] += dp[a - coin];

// Swapped: counts every ORDERING of the same coins separately -- a
// different (larger) number, even though the recurrence LOOKS identical.

Used-at-most-once: Partition Equal Subset Sum's direction trap

Partition Equal Subset Sum reduces to subset-sum: is some subset achievable summing to half the total? The 0/1 knapsack table for this has the same easy-to-miss trap in the *opposite* direction from Coin Change's loop-order issue: the achievable-sum range must be iterated downward for each number, so a number never combines with a sum that was updated using that same number earlier in the same pass. Iterate upward by mistake, and a single number quietly becomes reusable — the unbounded-knapsack answer, not the 0/1 one.

Two running values instead of one: Maximum Product Subarray

Maximum Subarray (Kadane's algorithm) tracks one running value — the best sum ending here. Maximum Product Subarray looks identical at first glance, but multiplication has a trap addition doesn't: a negative number can flip the sign of everything that follows, turning the current running *minimum* (a large-magnitude negative product) into the new *maximum*. The fix is tracking both a running max and a running min at every step, and computing the next max/min from *both* previous values — not just the previous max.

Common mistakes

• Reaching for recursion without a memo table — the recurrence itself is usually the easy part; forgetting to cache repeated subproblems is what turns a correct O(n) or O(n²) idea into an exponential one.
• Getting Coin Change II's loop order backwards — amount-outer, coin-inner silently counts permutations instead of combinations, with no crash or obviously wrong-looking output to flag it.
• Iterating the wrong direction in a 0/1 knapsack table — upward iteration silently allows reuse of an item that should only be usable once.
• Tracking only a running max for a product-based recurrence — Maximum Product Subarray needs the running min too, since a negative multiplier can make the current worst value become the new best.