State Machine Dynamic Programming: Modeling Complex Action Transitions & Cooldowns

1. Modeling Problems as Finite State Automata

Consider algorithmic trading on an asset over N days with price array prices. The investor is bound by three strict business rules:

1. You may only hold at most one share of stock at any given moment.
2. After selling stock on day i, you cannot buy stock on day i + 1 (mandatory 1-day cooldown).
3. You may complete as many transactions as you desire.

A monolithic state dp[i] fails because whether we can buy on day i depends on whether a sale occurred on day i - 1. To solve this, we construct a 3-state finite automaton:

2. Recurrence Relations & Mathematical Derivation

For each day i ∈ [0, N - 1], the maximum capital in each state is derived as follows:

Base Cases (Day 0):

• hold[0] = -prices[0] (Buying the stock requires upfront capital).
• sold[0] = 0 (Cannot sell stock that has not yet been acquired).
• cooldown[0] = 0 (Starting day idling with zero transactions).

The maximum profit attainable after N days is max(sold[N - 1], cooldown[N - 1]), as ending in a hold state leaves unliquidated capital locked in depreciable stock.

3. O(1) Constant Auxiliary Space Compression

Observing the recurrence equations demonstrates that day i values depend solely on day i - 1. We collapse the entire O(N) table into three 64-bit scalar registers:

int maxProfitWithCooldown(const vector<int>& prices) {
    if (prices.empty()) return 0;
    int hold = -prices[0];
    int sold = 0;
    int cooldown = 0;

    for (size_t i = 1; i < prices.size(); ++i) {
        int prevHold = hold;
        int prevSold = sold;
        int prevCooldown = cooldown;

        hold = max(prevHold, prevCooldown - prices[i]);
        sold = prevHold + prices[i];
        cooldown = max(prevCooldown, prevSold);
    }

    return max(sold, cooldown);
}

4. Generalized K-Day Cooldown via State Delay Queues

When business rules expand the post-sale freeze from 1 day to an arbitrary K-day lockout, a naive state machine requires K + 2 distinct automaton states. Instead of allocating separate variables for each cooldown day, high-throughput engines model this using a circular delay line or rolling vector:

This maintains the strict invariant that profits from sales executed within the prior K days cannot fund new purchases until the delay queue matures, executing in O(N) time and O(K) auxiliary memory.

5. The K-Transactions Paradigm: Dual Indexing & 2K+1 Finite States

When the total allowable transactions are restricted to at most K, state space expands along two dimensions: temporal progression (day i) and quota consumption (transaction k ∈ [1, K]). Each transaction k splits into two coupled states:

• hold[k]: Maximum balance after purchasing stock for the k-th time. Derived as max(hold[k], cash[k - 1] - prices[i]).
• cash[k]: Maximum balance after selling stock for the k-th time. Derived as max(cash[k], hold[k] + prices[i]).

If K ≥ N / 2, the quota constraint becomes redundant, since one can execute at most N / 2 complete roundtrips. Under this condition, the algorithm immediately degenerates to unconstrained greedy trading (Stock II), executing in O(N) time with zero auxiliary memory.

6. Transaction Fees vs. Cooldown: Structural Duality

Both transaction fees and cooldowns act as friction mechanisms to penalize hyperactive trading:

• Transaction Fee (Monetary Friction): Charges a scalar penalty per roundtrip trade. It penalizes micro-fluctuations where price delta ΔP ≤ fee, pruning unprofitable low-amplitude trades.
• Cooldown Period (Temporal Friction): Charges a temporal penalty per roundtrip trade. It penalizes quick roundtrips that risk missing massive upcoming macro-trends during the mandatory lockout window.

By combining both friction models into a single unified 3-state recurrence, quantitative trading models prevent both over-trading transaction cost erosion and unfavorable market re-entry timing.

7. Engineering Invariants & Edge Case Handling

• Strict Initialization with Negative Infinity: When initializing state arrays or registers, states that represent impossible initial scenarios (such as selling before buying) must be initialized to -∞ (or INT_MIN / 2 to prevent arithmetic underflow when subtracting prices). Initializing to 0 erroneously allows phantom sales on day 0.
• Monotonically Decreasing Price Sequences: If stock prices drop every single day (e.g., [9, 8, 7, 5, 2]), the globally optimal strategy is to execute zero transactions. The algorithm must gracefully return 0 rather than forcing an unprofitable purchase and sale.

8. Algorithmic Comparison: Stock Trading DP Family