LC Patterns — 1D Dynamic Programming

Bottom-up with rolling variables (the shape of Patterns 1–3)

int prev2 = base0, prev1 = base1;
for (int i = 2; i <= n; ++i) {
    int cur = combine(prev1, prev2, cost(i));
    prev2 = prev1; prev1 = cur;
}
return prev1;

Top-down memoization (derive-first form)

int solve(int i, vector<int>& memo) {
    if (i <= base_i) return base_val;
    int &res = memo[i];
    if (res != -1) return res;
    return res = combine(solve(i-1, memo), solve(i-2, memo));
}

Universal pitfalls

1. Fuzzy state. If you can't define dp[i] in one sentence, stop and fix that — the transition can't be right if the state is vague. Common precision trap: "best ending at i" (Kadane, LIS) vs "best up to i" (robber) are different states with different answers.
2. Indexing convention drift: dp[i] = "first i characters" (size n+1, dp[0] = empty) vs "ending at index i" (size n). Pick per problem, write it as a comment, never mix.
3. Sentinel arithmetic: INT_MAX for "impossible" then dp[j] + cost overflows. Guard: if (dp[j] != INT_MAX) ... — or use a huge-but-safe constant like 1e9.
4. Wrong inner-loop direction in compressed knapsack (Pattern 6) — backwards for 0/1, forwards for unbounded. The single most-tested DP mechanic.
5. Loop order changes the meaning (Pattern 5): coins-outer counts combinations; amount-outer counts permutations. Not a style choice — a semantics choice.
6. Answer location (framework Q5): forgetting the max over all positions when the state is "ending at i".

What it is: The number of ways (or min cost) to reach step i depends only on the last one or two steps: dp[i] = dp[i-1] + dp[i-2] (count) or dp[i] = cost[i] + min(dp[i-1], dp[i-2]) (cost). The "hello world" of DP — use it to drill the 5-question framework until it's reflexive.

Intuition: Split all the ways to reach step i by the last move (you came from i−1, or from i−2). The cases don't overlap and cover everything, so counts add and costs min. Every counting DP is this move: split by the last decision.

Approach:

int climbStairs(int n) {
    int p2 = 1, p1 = 1;                     // ways to reach step 0, step 1
    for (int i = 2; i <= n; ++i) { int c = p1 + p2; p2 = p1; p1 = c; }
    return p1;
}

O(n) time, O(1) space via rolling variables.

What it is: At each element you choose take it (earning its value but forfeiting the neighbor) or skip it. dp[i] = max(dp[i-1], dp[i-2] + val[i]) — the better of skipping i, or taking i on top of i−2's best.

Intuition: The constraint ("no two adjacent") only couples neighbors, so the whole future depends on just one bit of the past: did I take the previous element? That collapses exponential choice into two rolling values. Learn the two costume variants: circular arrays (first and last are adjacent → run the linear DP twice, once excluding the first house and once excluding the last, take the max) and value-domain transforms (740: taking value v deletes v±1 → total the points per value, and it is house robber on the value axis).

Approach:

int rob(vector<int>& a) {
    int skip = 0, take = 0;                  // best excluding / including previous
    for (int x : a) { int nskip = max(skip, take); take = skip + x; skip = nskip; }
    return max(skip, take);
}

What it is: For max-subarray-type problems: best_ending_here = max(x, best_ending_here + x) — at each element, either extend the running subarray or restart at this element; the answer is the max over all positions.

Intuition: State precision is everything: dp[i] = best subarray ending exactly at i (not "up to i"). With that state, the choice is binary — a subarray ending at i is either {x} alone or an extension of the best one ending at i−1. A negative running best can never help an extension → restart. For products (152), sign flips mean the minimum can become the maximum after multiplying by a negative — track both. For circular (918), max-circular = total − min-subarray (the complement trick), with an all-negative guard.

Approach:

int maxSubArray(vector<int>& a) {
    int best = a[0], cur = a[0];
    for (int i = 1; i < (int)a.size(); ++i) {
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    return best;
}

What it is: Can (or in how many ways can) the first i characters be split into valid pieces? dp[i] aggregates over every valid last piece s[j..i): dp[i] |= dp[j] && valid(s[j..i)) (feasibility) or dp[i] += dp[j] · ways(piece) (counting).

Intuition: Split by the last piece — the same move as Pattern 1, but the "last step" is now a variable-length chunk validated by a dictionary or a decoding rule. dp[0] = true/1 (the empty prefix) is what makes the first piece work — the base case is the design here.

Approach:

bool wordBreak(string s, vector<string>& dict) {
    unordered_set<string> words(dict.begin(), dict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;                                 // empty prefix
    for (int i = 1; i <= n; ++i)
        for (int j = i - 1; j >= 0 && !dp[i]; --j)   // j = start of last piece
            dp[i] = dp[j] && words.count(s.substr(j, i - j));
    return dp[n];
}

Prune the inner loop by the max dictionary word length. Decode Ways (91) is the same skeleton with pieces of length 1–2 and validity rules ('0' can't stand alone, "10"–"26" for pairs). Min-cut palindrome partitioning (132) = same 1D skeleton where valid = palindrome and aggregation = min(dp[j] + 1).

What it is: dp[a] = best/count for amount a, where each item can be used unlimited times: dp[a] = min(dp[a - coin] + 1) over coins (fewest coins) or dp[a] += dp[a - coin] (count). The state is a value, not an array index — the second big family of 1D states.

Intuition: Split by the last coin used. The subtle-but-crucial point is loop order semantics: coins outer / amount inner ⇒ each combination counted once, in a canonical coin order (518: combinations); amount outer / coins inner ⇒ different orderings counted separately (377: permutations). Same two loops, swapped, different universe — being able to explain why (the outer-coins loop fixes the order in which coin types may appear) is the interview differentiator.

Approach:

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && dp[a - c] != INF)
                dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] == INF ? -1 : dp[amount];
}

What it is: Each item usable at most once: can some subset hit target sum t (416), or reach a target with ± signs (494)? The 2D dp[item][sum] compresses to a 1D boolean/count array over sums — with the inner loop running backwards.

Intuition: In-place compression means dp[s] holds "previous row" values until overwritten. Iterating sums descending reads dp[s - x] from the previous item-row (this item not yet applied) — so each item is used ≤ once. Ascending would read the current row — the item gets reused, which is Pattern 5. One loop direction is the entire difference between 0/1 and unbounded knapsack; interviewers test exactly this, and "why backwards?" is the follow-up. The transforms: 494 reduces to "count subsets summing to (total + target)/2"; 1049 to "split stones into two near-equal halves."

Approach:

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2) return false;
    int target = total / 2;
    vector<char> dp(target + 1, 0);
    dp[0] = 1;                                    // empty subset
    for (int x : nums)
        for (int s = target; s >= x; --s)         // BACKWARDS: each item once
            dp[s] = dp[s] | dp[s - x];
    return dp[target];
}

What it is: dp[i] = best chain ending at i, computed by scanning all previous j and extending any compatible one: dp[i] = max(dp[j]) + 1 over j < i, a[j] < a[i]. O(n²) baseline; the classic follow-up compresses to O(n log n) with the patience-sorting tails array + binary search.

Intuition: Unlike Patterns 1–3 (fixed lookback), here any earlier index may be the predecessor — that's what costs the inner loop. The O(n log n) insight: you don't need every dp[j], only, for each chain length, the smallest possible tail — and that tails array is provably sorted, so each element binary-searches its slot. The counting variant (673) carries a second array cnt[i] alongside dp[i].

Approach:

int lengthOfLIS(vector<int>& a) {
    vector<int> tails;                        // tails[k] = min tail of an inc. subseq of length k+1
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;                         // improve the tail for this length
    }
    return tails.size();
}

What it is: The 1D index is time (days), but at each step you're in one of a few named states (holding a stock / not holding / cooling down), each with its own dp value. Transitions are the allowed moves between states with their profits/costs — literally draw the state diagram, then transcribe it into one rolling variable per state.

Intuition: When "what am I allowed to do next?" depends on a small piece of history (do I hold? did I just sell?), don't fight it — name the states and give each its own recurrence. The diagram is the derivation: nodes = states, edges = buy/sell/rest with weights ±price. Cooldown (309) adds a third node; a transaction fee (714) is one extra term on the sell edge; the same idiom scales to "at most k transactions" by multiplying states.

Approach (309, cooldown):

int maxProfit(vector<int>& p) {
    int hold = INT_MIN, sold = 0, rest = 0;   // states after today's action
    for (int x : p) {
        int prevSold = sold;
        sold = hold + x;                      // sell today
        hold = max(hold, rest - x);           // keep holding, or buy (from rest only)
        rest = max(rest, prevSold);           // idle; cooldown feeds rest next day
    }
    return max(sold, rest);
}

What it is: Reachability/min-steps along an array where each cell says how far you can move next. The O(n²) DP ("for each i, try all previous jumpers") is the derivation, but the accepted solutions collapse it: reachability (55) → a running farthest-reach greedy; min jumps (45) → BFS-layers-in-disguise greedy; constrained variants (1871) → DP + a sliding-window count of reachable predecessors.

Intuition: This pattern earns its place by teaching the boundary between DP and greedy: when the transition has dominance structure ("a farther reach dominates a nearer one — nothing a nearer reach enables is lost"), the DP's inner loop collapses to O(1) greedy state. When dominance fails (weighted/conditional variants), you fall back to the DP — and if the transition window is a contiguous range, a sliding-window sum or monotonic deque rescues O(n). Being able to say why greedy is safe (an exchange argument) is what separates memorized greedy from derived greedy.

Approach (45, min jumps as implicit BFS layers):

int jump(vector<int>& a) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < (int)a.size(); ++i) {
        farthest = max(farthest, i + a[i]);
        if (i == curEnd) { ++jumps; curEnd = farthest; }   // finished a BFS layer
    }
    return jumps;
}