L35 · DP III — Take / Skip Decisions

Series: LeetCode — From Basics to Interview-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 interviews, 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])     # or dp[i - k] if taking blocks k
        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 finished yesterday's cooldown.

The final answer is max(sold, rest) and never hold. Ending the sequence still holding a share means you spent money and never recovered it, which is never optimal.

The reachability variant, where the value is 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]

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 at day 0: hold[0] = -prices[0] (I bought), sold[0] = 0 — actually buying and selling on day 0 nets zero, so 0 is defensible, but -inf is cleaner because it makes the "impossible so far" cases explicit and prevents a spurious transition. rest[0] = 0.

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.

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. Without the prev_* snapshot, sold = hold + p reads today's hold, permitting buy-and-sell on the same day. Snapshot all three before updating any.

Returning max(hold, sold, rest). Ending while holding is never optimal — you paid for a share and never sold it. Including hold in the final max can only return a smaller number when prices are all rising, so it is a wrong answer, not a harmless one.

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 that do not change the legal move set. Tracking "number of days since I last bought" when only the last action matters multiplies the state space for nothing.

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: O(n² · L) time where L is the maximum word length, or O(n³) if you count string slicing as O(n). There are n states, each transition scans up to n split points, and each s[j:i] in words costs O(i − j) to hash the slice. Space is O(n) for the dp array plus O(total dictionary characters) for the set.

You can cut the inner loop by only trying split points where i − j is at most the longest dictionary word, which is a real speedup when words are short relative to s.

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.

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.