DP III — Take / Skip Decisions

Review boundary and corrected contracts

Cooldown transitions read a complete snapshot of yesterday to prevent buying immediately after selling. Word Break slices and hashes variable-length substrings: the shown unrestricted nested loops can require O(n³) character work, not O(n²). Stock prices and jump lengths are nonnegative. canJump_dp requires a nonempty list; an empty list has no starting/target index and is outside its contract. The stock routine returns 0 on empty prices, and Word Break treats the empty string as segmentable.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Recognise the take-or-skip shape, add a state dimension when one index is not enough to describe the situation, and know when a DP problem is secretly a greedy one.

Series: LeetCode — From Basics to Production-Ready · Session 35 / 65 · Phase 2 · Dynamic programming

Why this session exists

"At each step I either do X or I don't" is the most common DP shape in practice, and it is worth studying as a shape rather than as a list of problems. Once you see it, the recurrence writes itself: dp[i] = best(take, skip).

But there is a complication that session 34 did not have, and it is the real content of this session. Sometimes the index alone is not enough to describe your situation. In the stock problem with cooldown, "I am at day 5" does not determine what I can do — it matters whether I am currently holding a share, and whether I just sold. Same index, three different situations, three different legal moves.

That is when you add a state dimension. The state becomes (index, mode) rather than just index. Knowing when to do this — and resisting the urge to do it when it is unnecessary — is the skill that separates people who can do medium DP from people who can do hard DP.

The third theme is a warning. Jump Game looks like DP, has a clean DP solution, and has a greedy solution that is strictly better. Knowing when the DP is not the intended answer matters.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

dp[i] = max(take, skip)

Concretely: write the three-state stock machine. Three arrays or three variables — hold, sold, rest — and the transitions between them. Do not look at the code below first.

What wobbles: which state can transition into hold. After selling you must rest for a day, so hold can be entered from rest but never directly from sold. Getting that edge wrong produces an answer that is too high and looks plausible.

Pattern anatomy

The shape of problem that summons take/skip DP: a linear sequence where at each position you make a binary choice, and the choice may impose a constraint on what is legal afterwards. If the constraint reaches exactly one step back, one index suffices — that was session 34. If the constraint depends on what you did, not just where you are, you need a mode dimension.

The invariant when you add a dimension: dp[i][s] is the best achievable value considering positions 0..i, given that you end position i in situation s. Every transition into s must be legal from the situation you came from. Writing that sentence for each state is what prevents the illegal-edge bug.

The basic template, one dimension:

def take_skip(items):
    n = len(items)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        skip = dp[i - 1]
        take = dp[i - 1] + value(items[i - 1])     # choose the predecessor from the actual exclusion rule
        dp[i] = max(skip, take)
    return dp[n]

The state-machine template, for the cooldown problem:

def maxProfit(prices):
    if not prices:
        return 0
    hold = float("-inf")     # currently own a share
    sold = float("-inf")     # just sold today (cooldown tomorrow)
    rest = 0                 # own nothing, free to buy
    for p in prices:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - p)      # keep holding, or buy from rest
        sold = prev_hold + p                      # can only sell if you were holding
        rest = max(prev_rest, prev_sold)          # stay free, or cooldown finishes
    return max(sold, rest)                        # never end holding a share

Three lines, three states, and every edge is a claim about legality.

• hold = max(prev_hold, prev_rest - p) — you either already held, or you bought today. Buying is legal only from rest, not from sold, because selling forces a cooldown day. This is the edge that encodes the entire cooldown rule.
• sold = prev_hold + p — you can only sell what you hold. There is no max here because there is exactly one way to be in the sold state.
• rest = max(prev_rest, prev_sold) — you were already free, or you sold yesterday and finished today's cooldown.

The final answer is max(sold, rest) and never hold. For nonnegative prices, removing an unmatched final buy leaves a legal no-holding schedule with at least as much cash. Holding is therefore not needed in the final maximum (it can tie when the price is zero).

The reachability variant, for a nonempty list of nonnegative maximum jump lengths, uses a boolean rather than a number:

def canJump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True
    for i in range(1, n):
        for j in range(i):
            if dp[j] and j + nums[j] >= i:
                dp[i] = True
                break
    return dp[n - 1]

The greedy compression keeps a reachable prefix: after scanning reachable indices before i, every index from 0 through furthest can be reached because jumps may have any length up to the stated maximum. If i exceeds that frontier, no earlier reachable index can cross the gap.

def canJump_greedy(nums):
    # Same nonempty, nonnegative-input contract as canJump_dp.
    furthest = 0
    for i, jump in enumerate(nums):
        if i > furthest:
            return False
        furthest = max(furthest, i + jump)
        if furthest >= len(nums) - 1:
            return True
    return False

This fails correctly on [3, 2, 1, 0, 4]: the frontier stays at 3, so index 4 is unreachable. [0] succeeds because the start is already the target.

And the split-point variant, where the transition scans all earlier positions:

def wordBreak(s, wordDict):
    words = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                                  # empty prefix is always breakable
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

dp[0] = True is the base case that makes everything work — the empty string is trivially segmentable, and without it no dp[i] can ever become True.

The cue

You are looking at a take/skip DP when the statement contains one of these tells:

1. A binary action per element. Buy or don't, take or don't, cut here or don't, include or exclude.
2. A constraint that depends on your recent action rather than your position. "Cooldown of one day", "cannot buy immediately after selling", "must wait k steps". That is the mode-dimension signal.
3. "Can you reach / can you form / is it possible" with boolean answers instead of numeric ones. Same recurrence shape, or instead of max.
4. Splitting a string or array into valid pieces. Word Break, Palindrome Partitioning II, Decode Ways. The transition is "for every split point j, is the prefix good and the piece j..i valid".
5. Transaction limits. "At most k transactions" adds a third dimension: (day, transactions_used, holding).

The negative cue that matters most here: if a greedy sweep provably works, use it. Jump Game has a two-line greedy that is O(n) time and O(1) space, against O(n²) and O(n) for the DP. Offering the DP when the greedy exists is a weaker answer. The test for whether greedy applies is whether a locally optimal choice is provably globally optimal — for Jump Game, tracking the furthest reachable index never discards a better option, because reachability is monotone.

Guided solve

Best Time to Buy and Sell Stock with Cooldown. You may complete as many transactions as you like, but after you sell you must wait one day before buying again. You may not hold more than one share at a time. Maximise profit.

Start with why one index is not enough. Suppose I tell you it is day 5. Can you tell me what moves are legal? No — if I am holding a share I can sell or keep holding; if I sold yesterday I can only rest; if I am free I can buy or rest. Three different answers at the same index. The index does not determine the legal move set, therefore the index is not a sufficient state. That sentence is the entire justification for adding a dimension, and it is what you should say out loud.

So enumerate the situations. What can be true at the end of day i?

• hold — I own a share.
• sold — I sold today, so tomorrow is a cooldown.
• rest — I own nothing and I am free to buy tomorrow.

Three states, and they are exhaustive and mutually exclusive. Now define each precisely:

hold[i] = max profit through day i given I end day i owning a share. sold[i] = max profit through day i given I sold on day i. rest[i] = max profit through day i given I own nothing and did not sell today.

Now derive each transition by asking: what is the last thing that happened to put me in this state?

To end day i holding: either I was already holding yesterday and did nothing, giving hold[i-1]; or I bought today, which requires being free yesterday, giving rest[i-1] - prices[i]. Buying from sold[i-1] is illegal — that is the cooldown.

To end day i having sold: I must have been holding yesterday and sold today. Exactly one predecessor, so sold[i] = hold[i-1] + prices[i].

To end day i free and not-just-sold: either I was already free, giving rest[i-1]; or I sold yesterday and today's cooldown has now elapsed, giving sold[i-1].

Base cases before any day: hold and sold are -inf, rest is 0. After day 0, hold[0] = -prices[0], sold[0] = -inf, and rest[0] = 0. Under this one-action-per-day state definition, selling on day 0 is unreachable; a zero sentinel may preserve the final optimum here but does not represent that state exactly.

The rolling form is the code above. The prev_* snapshot is mandatory: sold must read yesterday's hold, and if you have already overwritten hold on this iteration you read today's value and allow buying and selling on the same day.

Trace on [1, 2, 3, 0, 2]. Day 0: hold −1, sold −inf, rest 0. Day 1: hold max(−1, 0−2) = −1; sold −1+2 = 1; rest max(0, −inf) = 0. Day 2: hold max(−1, 0−3) = −1; sold −1+3 = 2; rest max(0, 1) = 1. Day 3: hold max(−1, 1−0) = 1; sold −1+0 = −1; rest max(1, 2) = 2. Day 4: hold max(1, 2−2) = 1; sold 1+2 = 3; rest max(2, −1) = 2. Answer max(3, 2) = 3, which matches buy at 1, sell at 2, cooldown, buy at 0, sell at 2.

A state must determine future legality, rewards and successor states, not just the names of currently available actions. Two histories with the same future possibilities can share a state, retaining the best profit so far. Holding and being free differ here. Other problems may need a budget or transaction count even when the immediate action names coincide; omit a dimension only after proving future equivalence or dominance.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• Jump Game — write the O(n) greedy, not the O(n²) DP. Track a single number: the furthest index reachable so far. Think about what condition means you are stuck.
• Word Break — dp[i] should mean "the first i characters can be segmented". Work out the base case before anything else, and convert the dictionary to a set before the loop.

If both land early, do Best Time to Buy and Sell Stock II (unlimited transactions, no cooldown) and note how the state machine collapses to two states — and that a greedy summing every positive daily delta also works. Comparing the two is instructive.

Common failure modes

Allowing hold to be entered from sold. Breaks the cooldown rule and inflates the profit. The result looks like a plausible answer, which is what makes it dangerous.

Overwriting a state before another transition reads it. Replacing only sold = prev_hold + p by sold = hold + p makes day-0 sold equal 0 instead of unreachable: it permits a same-day buy/sell in the intermediate state. That particular mutation need not change the final profit under nonnegative prices, so it is not a demonstrated wrong-answer example. By contrast, adding prev_sold - p to the hold candidates violates the cooldown and yields 4 instead of 3 on [1, 2, 3, 0, 2]. Snapshot yesterday's values to preserve the stated state meanings.

Misexplaining the terminal maximum. Adding an argument to max cannot lower its result. For nonnegative prices, hold is dominated by a legal non-holding schedule obtained by omitting its final buy, so max(hold, sold, rest) has the same numeric answer. Returning only max(sold, rest) expresses the terminal contract more directly; it is not a bug fix to the inclusive maximum under these assumptions.

Base case dp[0] = False in Word Break. The empty prefix must be True or nothing bootstraps and the answer is always False.

Leaving the dictionary as a list in Word Break. s[j:i] in word_list is O(len(list) × len(word)) instead of O(len(word)). It turns an O(n²·L) solution into something much worse and TLEs.

Writing the O(n²) DP for Jump Game. Correct but strictly dominated. The greedy is shorter, faster, and demonstrates better judgement.

Adding dimensions without a future distinction. In this model, purchase age does not affect future legality or rewards once day and holding mode are known; keep the best profit in that mode instead. A different problem with age-dependent fees would need that history.

Myth: If one index is not enough to describe the state, the problem must need a fundamentally more complex algorithm.

Why: It often needs one more dimension. The state is whatever determines future actions, their rewards and successor situations — if the index alone is insufficient, enumerate those situations and index by (position, situation). The cooldown stock problem goes from one array to three, and the recurrence in each is still a one-line max. The algorithm did not get harder; the state got more precise. People who freeze here are treating 'add a dimension' as an exotic technique instead of the routine response to an underspecified state.

Steps 1: Because every decision is binary, the set of outcomes at each index partitions cleanly into the take branch and the skip branch.

Steps 2: Because a DP state must determine the legal set of next actions, any two situations permitting different next actions must be distinct states.

Steps 3: Because at day i the moves available differ according to whether you hold, just sold, or are free, the index alone is insufficient and a second dimension is required.

Steps 4: Because each of the three states has a small fixed number of legal predecessors, each transition is an O(1) max over at most two candidates.

Steps 5: Because there are 3n states and each costs O(1), the whole computation is O(n) despite the added dimension — dimensions multiply the state count, they do not change the per-state cost.

Steps 6: Therefore the testable prediction is that on prices = [1, 2, 3, 0, 2] the three-state machine yields 3, while removing the cooldown edge — allowing hold to be entered from sold — yields 4, which corresponds to an illegal schedule.

Picture: A three-room machine. You are always standing in exactly one room: Holding, Just-Sold, or Free. Each day a door opens and you may move along the arrows that exist. There is deliberately no arrow from Just-Sold to Holding — that missing arrow is the cooldown rule, drawn rather than written.

Trigger: Fires when the legal moves at a position depend on what you did recently, not just where you are — cooldowns, gaps, mandatory waits, transaction limits.

Name: Single-dimension dp[i]

Gain: Smallest state space; simplest code; O(1) space after collapsing

Cost: Silently wrong when the constraint depends on your recent action rather than your position — and the wrongness looks like a plausible number

Name: State machine dp[i][mode]

Gain: Three modes handle this one-day cooldown with O(1) rolling space. A transaction-limit variant also needs a count axis and generally O(k) rolling storage.

Cost: More states to define and more edges to justify; every missing or spurious edge is a silent wrong answer

Name: Greedy sweep

Gain: O(n) time, O(1) space, two or three lines

Cost: Requires a proof that local optimality implies global optimality; wrong on most take/skip problems and there is no error to warn you

Pick: Greedy only when you can state the exchange argument out loud — for Jump Game, that reachability is monotone so tracking the furthest reachable index never discards a better option. Single-dimension DP when the index alone determines the legal move set. Add a mode dimension the moment two different histories at the same index permit different next actions.

Complexity

Cooldown stock: O(n) time, O(1) space. There are 3n states — three per day — and each transition is a max over at most two candidates, so O(1) each. Three states times O(1) times n days is O(n). The rolling form keeps only three scalars.

This is worth stating explicitly because it surprises people: adding a state dimension multiplied the state count by 3, a constant, so the asymptotic complexity did not move. Dimensions are only expensive when the new dimension's size grows with the input — (day, transactions) with k transactions gives O(n·k), which does grow.

Word Break as written: O(n³) character work in the worst case, with expected hash-set lookup after hashing. Each of O(n²) candidate split pairs can allocate and hash a slice of length up to n, even when that slice is longer than every dictionary word. The longest dictionary word L therefore does not bound the slice cost in this unrestricted code. Building the set costs O(D) character hashing work for D total dictionary characters; auxiliary space is O(n + k) references/cells plus an O(n) temporary slice for k distinct dictionary words (O(n + D) is a safe representation-level bound).

Restricting j to max(0, i-L)..i-1 bounds both candidate count and slice length by L, giving O(n·L² + D) character work for that modified version. This optimization is not present in the unrestricted code above.

Jump Game: O(n²) time, O(n) space for the DP; O(n) time, O(1) space for the greedy. The greedy is strictly better on both axes, which is the whole reason it is the expected answer.

Self-check (answer follows each question).

Q: In the cooldown stock problem, why is one index insufficient as a DP state?

A: Because the legal moves at day i depend on whether you are holding, just sold, or free — three different move sets at the same index. A state must determine the legal next actions, so the index alone is underspecified.

Q: Which transition edge encodes the cooldown rule, and what happens if you add the missing one?

A: The absence of an edge from sold to hold: you may only buy from rest. Adding sold → hold permits buying the day after selling, which inflates the profit and corresponds to an illegal schedule.

Q: Why is the final answer max(sold, rest) rather than max(hold, sold, rest)?

A: The required answer is realized cash without an unsold share. With nonnegative prices, omitting an unmatched final buy yields a legal schedule with at least as much cash, so hold cannot increase the maximum; adding it cannot decrease a maximum either. The inclusive maximum is numerically equivalent here, but the two-state return states the contract explicitly.

Q: What is dp[0] in Word Break and why?

A: True. The empty prefix is trivially segmentable, and it is the base case that lets any longer prefix become True — without it, no dp[i] can ever be set.

Q: Why is the greedy solution preferred over DP for Jump Game?

A: It is O(n) time and O(1) space against O(n²) and O(n) for the DP, and it is provably correct because reachability is monotone — tracking the furthest reachable index never discards a better option.

Q: You are asked for 'at most k transactions'. How many dimensions does the state need, what is the complexity, and why is this different from the cooldown case?

A: Three: (day, transactions used, holding or not), giving O(n·k) states and O(n·k) time. It differs from cooldown because the new dimension's size grows with the input parameter k, whereas the cooldown mode had a fixed size of 3 and therefore vanished into the constant factor.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

The cooldown stock problem goes in the queue, and it is worth a shorter interval than most. The three-state machine is the prototype for every "at most k transactions" and "with transaction fee" variant, so the drill that pays is drawing the three boxes and the arrows between them before writing a line of code.

• Take-or-skip is the most common DP shape: dp[i] = best(take, skip). Recognise it and the recurrence writes itself.

• A state must determine future moves, rewards and successor states. Different legal moves imply distinct situations; equal action names alone do not prove that histories can be merged.

• The cooldown rule is a missing edge, not extra code: hold is reachable from rest but never from sold.

• Snapshot all states before updating any. Reading a same-iteration value permits buying and selling on the same day.

• Adding a fixed-size mode dimension does not change the asymptotic complexity. Adding one whose size grows with the input does.

• Jump Game has a provable greedy. When local optimality is provably global, the DP is a weaker answer even though it is correct.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.