Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Stock DP
DSA

Stock DP

Learn DP techniques for stock trading problems with constraints on transactions, holding, and cooldowns.

The Stocks DP pattern is one of the most frequently asked Dynamic Programming patterns in interviews and competitive programming.

At its core, Stock DP asks:

“What is the maximum profit I can make under certain trading constraints?”

The key observation is that every day can be represented using a small number of states.

The most important states are:

hold = maximum profit while holding a stock
cash = maximum profit while not holding a stock

Additional constraints introduce additional states or dimensions:

Transactions → transaction count
Cooldown     → previous-day state
Fee          → modify buy/sell transition

Focus on recognizing:

“Buy → Hold → Sell → Buy…” = State Machine DP

Pattern Table

PatternTypical QuestionMain StateComplexity
Stock IOne transactionminPrice, profitO(n) / O(1)
Stock IIUnlimited transactionshold, cashO(n) / O(1)
Stock IIIAt most 2 transactionsTransaction statesO(n) / O(1)
Stock IVAt most K transactionsday × transaction × holdingO(nk)
CooldownCannot buy after sellinghold, sold, restO(n) / O(1)
Transaction FeeFee per transactionhold, cashO(n) / O(1)
Stock SpanPrevious smaller pricesMonotonic stackO(n) / O(n)

Mini Notes / Tips

### Tips

- First identify the states.
- The most common states are:
  - holding a stock
  - not holding a stock
- A transaction is usually considered complete when you SELL.
- For K transactions, use a transaction dimension.
- Cooldown requires an additional state or delayed transition.
- A transaction fee changes the buy/sell transition.
- Many stock problems can be reduced to O(1) space.
- Stock Span is NOT DP; it uses a monotonic stack.
- Never buy while already holding a stock.
- Never sell while not holding a stock.

1. Best Time to Buy & Sell Stock I

Single Transaction

This is the simplest stock problem.

You are allowed:

Buy once
Sell once

The important observation is that when selling today, we only need the minimum price seen before today.

State

minPrice
=
minimum price seen so far

profit
=
maximum profit found so far

Transition

minPrice = min(minPrice, price)

profit =
max(
    profit,
    price - minPrice
)

Java Template

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int profit = 0;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        profit = Math.max(profit, price - minPrice);
    }

    return profit;
}
def maxProfit(prices):
    min_price = float('inf')
    profit = 0

    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)

    return profit
int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int profit = 0;

    for (int price : prices) {
        minPrice = min(minPrice, price);
        profit = max(profit, price - minPrice);
    }

    return profit;
}
function maxProfit(prices) {
  let minPrice = Infinity;
  let profit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    profit = Math.max(profit, price - minPrice);
  }

  return profit;
}

Complexity

Time:  O(n)
Space: O(1)

Mental Trigger

“Buy once and sell once” → Minimum Price Tracking

2. Best Time to Buy & Sell Stock II

Unlimited Transactions

Now you can perform unlimited transactions, but you cannot hold multiple stocks simultaneously.

Instead of tracking individual transactions, use two states:

hold
cash

State Definition

hold
=
maximum profit while currently holding a stock

cash
=
maximum profit while currently holding no stock

Transitions

For every price:

hold =
max(
    hold,
    cash - price
)

Either:

  • continue holding, or
  • buy today.

For cash:

cash =
max(
    cash,
    hold + price
)

Either:

  • continue having no stock, or
  • sell today.

Java Template

public int maxProfit(int[] prices) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.length; i++) {
        int price = prices[i];

        int newHold = Math.max(hold, cash - price);
        int newCash = Math.max(cash, hold + price);

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
def maxProfit(prices):
    hold = -prices[0]
    cash = 0

    for i in range(1, len(prices)):
        price = prices[i]

        hold, cash = (
            max(hold, cash - price),
            max(cash, hold + price)
        )

    return cash
int maxProfit(vector<int>& prices) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.size(); i++) {
        int price = prices[i];

        int newHold = max(hold, cash - price);
        int newCash = max(cash, hold + price);

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
function maxProfit(prices) {
  let hold = -prices[0];
  let cash = 0;

  for (let i = 1; i < prices.length; i++) {
    const price = prices[i];

    const newHold = Math.max(hold, cash - price);
    const newCash = Math.max(cash, hold + price);

    hold = newHold;
    cash = newCash;
  }

  return cash;
}

Complexity

Time:  O(n)
Space: O(1)

Mental Trigger

“Unlimited transactions” → Hold/Cash State Machine

3. Best Time to Buy & Sell Stock III

At Most Two Transactions

Now there is a limit:

At most 2 complete transactions

A transaction is:

BUY → SELL

The simplest optimized solution maintains four states:

buy1
sell1
buy2
sell2

State Definition

buy1
=
maximum profit after first buy

sell1
=
maximum profit after first sell

buy2
=
maximum profit after second buy

sell2
=
maximum profit after second sell

Transitions

buy1  = max(buy1, -price)

sell1 = max(sell1, buy1 + price)

buy2  = max(buy2, sell1 - price)

sell2 = max(sell2, buy2 + price)

Java Template

public int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE;
    int sell1 = 0;

    int buy2 = Integer.MIN_VALUE;
    int sell2 = 0;

    for (int price : prices) {
        buy1 = Math.max(buy1, -price);
        sell1 = Math.max(sell1, buy1 + price);

        buy2 = Math.max(buy2, sell1 - price);
        sell2 = Math.max(sell2, buy2 + price);
    }

    return sell2;
}
def maxProfit(prices):
    buy1 = float('-inf')
    sell1 = 0

    buy2 = float('-inf')
    sell2 = 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)

        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2
int maxProfit(vector<int>& prices) {
    int buy1 = INT_MIN;
    int sell1 = 0;

    int buy2 = INT_MIN;
    int sell2 = 0;

    for (int price : prices) {
        buy1 = max(buy1, -price);
        sell1 = max(sell1, buy1 + price);

        buy2 = max(buy2, sell1 - price);
        sell2 = max(sell2, buy2 + price);
    }

    return sell2;
}
function maxProfit(prices) {
  let buy1 = -Infinity;
  let sell1 = 0;

  let buy2 = -Infinity;
  let sell2 = 0;

  for (const price of prices) {
    buy1 = Math.max(buy1, -price);
    sell1 = Math.max(sell1, buy1 + price);

    buy2 = Math.max(buy2, sell1 - price);
    sell2 = Math.max(sell2, buy2 + price);
  }

  return sell2;
}

Complexity

Time:  O(n)
Space: O(1)

Mental Trigger

“At most 2 transactions” → Multiple Buy/Sell States

4. Best Time to Buy & Sell Stock IV

At Most K Transactions

Stock III is just a special case of Stock IV:

K = 2

For arbitrary K, use:

dp[transaction][holding]

A convenient interpretation is:

dp[t][0] = maximum profit after at most t sells and not holding
dp[t][1] = maximum profit after at most t sells and holding

Transitions

Buy:

dp[t][1] =
max(
    dp[t][1],
    dp[t][0] - price
)

Sell:

dp[t][0] =
max(
    dp[t][0],
    previousDp[t - 1][1] + price
)

Because the same array is being updated, iterate t backwards when using the optimized 1D implementation.

Java Template

public int maxProfit(int k, int[] prices) {
    if (prices.length == 0 || k == 0) {
        return 0;
    }

    // If k is large enough, this behaves like unlimited transactions.
    if (k >= prices.length / 2) {
        return unlimitedTransactions(prices);
    }

    int[] buy = new int[k + 1];
    int[] sell = new int[k + 1];

    Arrays.fill(buy, Integer.MIN_VALUE / 2);

    for (int price : prices) {
        for (int t = k; t >= 1; t--) {
            sell[t] = Math.max(
                sell[t],
                buy[t] + price
            );

            buy[t] = Math.max(
                buy[t],
                sell[t - 1] - price
            );
        }
    }

    return sell[k];
}

private int unlimitedTransactions(int[] prices) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.length; i++) {
        int price = prices[i];

        int newHold = Math.max(hold, cash - price);
        int newCash = Math.max(cash, hold + price);

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
def maxProfit(k, prices):
    if not prices or k == 0:
        return 0

    # If k is large enough, this behaves like unlimited transactions.
    if k >= len(prices) // 2:
        return unlimited_transactions(prices)

    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)

    for price in prices:
        for t in range(k, 0, -1):
            sell[t] = max(
                sell[t],
                buy[t] + price
            )

            buy[t] = max(
                buy[t],
                sell[t - 1] - price
            )

    return sell[k]

def unlimited_transactions(prices):
    hold = -prices[0]
    cash = 0

    for i in range(1, len(prices)):
        price = prices[i]

        hold, cash = (
            max(hold, cash - price),
            max(cash, hold + price)
        )

    return cash
int maxProfit(int k, vector<int>& prices) {
    if (prices.empty() || k == 0) {
        return 0;
    }

    // If k is large enough, this behaves like unlimited transactions.
    if (k >= (int)prices.size() / 2) {
        return unlimitedTransactions(prices);
    }

    vector<int> buy(k + 1, INT_MIN / 2);
    vector<int> sell(k + 1, 0);

    for (int price : prices) {
        for (int t = k; t >= 1; t--) {
            sell[t] = max(
                sell[t],
                buy[t] + price
            );

            buy[t] = max(
                buy[t],
                sell[t - 1] - price
            );
        }
    }

    return sell[k];
}

int unlimitedTransactions(vector<int>& prices) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.size(); i++) {
        int price = prices[i];

        int newHold = max(hold, cash - price);
        int newCash = max(cash, hold + price);

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
function maxProfit(k, prices) {
  if (prices.length === 0 || k === 0) {
    return 0;
  }

  // If k is large enough, this behaves like unlimited transactions.
  if (k >= Math.floor(prices.length / 2)) {
    return unlimitedTransactions(prices);
  }

  const buy = new Array(k + 1).fill(-Infinity);
  const sell = new Array(k + 1).fill(0);

  for (const price of prices) {
    for (let t = k; t >= 1; t--) {
      sell[t] = Math.max(sell[t], buy[t] + price);
      buy[t] = Math.max(buy[t], sell[t - 1] - price);
    }
  }

  return sell[k];
}

function unlimitedTransactions(prices) {
  let hold = -prices[0];
  let cash = 0;

  for (let i = 1; i < prices.length; i++) {
    const price = prices[i];

    const newHold = Math.max(hold, cash - price);
    const newCash = Math.max(cash, hold + price);

    hold = newHold;
    cash = newCash;
  }

  return cash;
}

Complexity

Time:  O(nk)
Space: O(k)

Important Difference

Stock III:
K = 2
→ Can optimize to O(1) states.

Stock IV:
K is variable
→ Need a transaction dimension.

Mental Trigger

“At most K transactions” → Transaction × Holding DP

5. Best Time to Buy & Sell Stock with Cooldown

Cooldown After Selling

Suppose:

Buy → Sell → Cooldown → Buy

After selling, you cannot buy on the next day.

The normal hold/cash states are no longer enough because the previous day matters.

Use three states:

hold
sold
rest

State Definition

hold
=
holding a stock

sold
=
sold a stock today

rest
=
not holding and not in the sold-today state

Transitions

hold =
max(
    hold,
    rest - price
)
sold =
hold + price
rest =
max(
    rest,
    sold
)

The important part is:

You can buy only from rest, not directly after sold.

Java Template

public int maxProfit(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }

    int hold = -prices[0];
    int sold = 0;
    int rest = 0;

    for (int i = 1; i < prices.length; i++) {
        int price = prices[i];

        int newHold = Math.max(
            hold,
            rest - price
        );

        int newSold = hold + price;

        int newRest = Math.max(
            rest,
            sold
        );

        hold = newHold;
        sold = newSold;
        rest = newRest;
    }

    return Math.max(sold, rest);
}
def maxProfit(prices):
    if not prices:
        return 0

    hold = -prices[0]
    sold = 0
    rest = 0

    for i in range(1, len(prices)):
        price = prices[i]

        hold, sold, rest = (
            max(hold, rest - price),
            hold + price,
            max(rest, sold)
        )

    return max(sold, rest)
int maxProfit(vector<int>& prices) {
    if (prices.empty()) {
        return 0;
    }

    int hold = -prices[0];
    int sold = 0;
    int rest = 0;

    for (int i = 1; i < prices.size(); i++) {
        int price = prices[i];

        int newHold = max(
            hold,
            rest - price
        );

        int newSold = hold + price;

        int newRest = max(
            rest,
            sold
        );

        hold = newHold;
        sold = newSold;
        rest = newRest;
    }

    return max(sold, rest);
}
function maxProfit(prices) {
  if (prices.length === 0) {
    return 0;
  }

  let hold = -prices[0];
  let sold = 0;
  let rest = 0;

  for (let i = 1; i < prices.length; i++) {
    const price = prices[i];

    const newHold = Math.max(hold, rest - price);
    const newSold = hold + price;
    const newRest = Math.max(rest, sold);

    hold = newHold;
    sold = newSold;
    rest = newRest;
  }

  return Math.max(sold, rest);
}

Complexity

Time:  O(n)
Space: O(1)

Mental Trigger

“Cannot buy immediately after selling” → Add Cooldown State

6. Best Time to Buy & Sell Stock with Transaction Fee

Unlimited Transactions + Fee

Here transactions are unlimited, but every completed transaction has a fee.

The states remain:

hold
cash

Only the transition changes.

If the fee is paid when selling:

cash =
max(
    cash,
    hold + price - fee
)

Java Template

public int maxProfit(int[] prices, int fee) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.length; i++) {
        int price = prices[i];

        int newHold = Math.max(
            hold,
            cash - price
        );

        int newCash = Math.max(
            cash,
            hold + price - fee
        );

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
def maxProfit(prices, fee):
    hold = -prices[0]
    cash = 0

    for i in range(1, len(prices)):
        price = prices[i]

        hold, cash = (
            max(hold, cash - price),
            max(cash, hold + price - fee)
        )

    return cash
int maxProfit(vector<int>& prices, int fee) {
    int hold = -prices[0];
    int cash = 0;

    for (int i = 1; i < prices.size(); i++) {
        int price = prices[i];

        int newHold = max(
            hold,
            cash - price
        );

        int newCash = max(
            cash,
            hold + price - fee
        );

        hold = newHold;
        cash = newCash;
    }

    return cash;
}
function maxProfit(prices, fee) {
  let hold = -prices[0];
  let cash = 0;

  for (let i = 1; i < prices.length; i++) {
    const price = prices[i];

    const newHold = Math.max(hold, cash - price);
    const newCash = Math.max(
      cash,
      hold + price - fee
    );

    hold = newHold;
    cash = newCash;
  }

  return cash;
}

Complexity

Time:  O(n)
Space: O(1)

Mental Trigger

“Unlimited transactions + fee” → Hold/Cash DP with modified sell

7. Generic Stock State Machine

The previous problems are all variations of one model.

The fundamental state is:

day
+
holding
+
transaction information
+
special constraints

The generic conceptual state is:

dp[day][transactions][holding]

where:

holding = 0 → not holding
holding = 1 → holding

Generic Transition

Buy

dp[i][t][1] =
max(
    dp[i-1][t][1],
    dp[i-1][t][0] - price
)

Sell

If t represents completed transactions:

dp[i][t][0] =
max(
    dp[i-1][t][0],
    dp[i-1][t-1][1] + price
)

Generic Java Template

public int maxProfit(int[] prices, int k) {
    int n = prices.length;

    if (n == 0 || k == 0) {
        return 0;
    }

    int[][][] dp = new int[n][k + 1][2];

    // Holding a stock before any transaction.
    for (int t = 0; t <= k; t++) {
        dp[0][t][1] = -prices[0];
    }

    for (int day = 1; day < n; day++) {
        for (int t = 0; t <= k; t++) {

            // Do nothing.
            dp[day][t][0] = dp[day - 1][t][0];
            dp[day][t][1] = dp[day - 1][t][1];

            // Buy.
            dp[day][t][1] = Math.max(
                dp[day][t][1],
                dp[day - 1][t][0] - prices[day]
            );

            // Sell: completes one transaction.
            if (t > 0) {
                dp[day][t][0] = Math.max(
                    dp[day][t][0],
                    dp[day - 1][t - 1][1] + prices[day]
                );
            }
        }
    }

    return dp[n - 1][k][0];
}
def maxProfit(prices, k):
    n = len(prices)

    if n == 0 or k == 0:
        return 0

    dp = [[[0] * 2 for _ in range(k + 1)]
          for _ in range(n)]

    # Holding a stock before any transaction.
    for t in range(k + 1):
        dp[0][t][1] = -prices[0]

    for day in range(1, n):
        for t in range(k + 1):

            # Do nothing.
            dp[day][t][0] = dp[day - 1][t][0]
            dp[day][t][1] = dp[day - 1][t][1]

            # Buy.
            dp[day][t][1] = max(
                dp[day][t][1],
                dp[day - 1][t][0] - prices[day]
            )

            # Sell: completes one transaction.
            if t > 0:
                dp[day][t][0] = max(
                    dp[day][t][0],
                    dp[day - 1][t - 1][1] + prices[day]
                )

    return dp[n - 1][k][0]
int maxProfit(vector<int>& prices, int k) {
    int n = prices.size();

    if (n == 0 || k == 0) {
        return 0;
    }

    vector<vector<vector<int>>> dp(
        n,
        vector<vector<int>>(k + 1, vector<int>(2)));

    // Holding a stock before any transaction.
    for (int t = 0; t <= k; t++) {
        dp[0][t][1] = -prices[0];
    }

    for (int day = 1; day < n; day++) {
        for (int t = 0; t <= k; t++) {

            // Do nothing.
            dp[day][t][0] = dp[day - 1][t][0];
            dp[day][t][1] = dp[day - 1][t][1];

            // Buy.
            dp[day][t][1] = max(
                dp[day][t][1],
                dp[day - 1][t][0] - prices[day]
            );

            // Sell: completes one transaction.
            if (t > 0) {
                dp[day][t][0] = max(
                    dp[day][t][0],
                    dp[day - 1][t - 1][1] + prices[day]
                );
            }
        }
    }

    return dp[n - 1][k][0];
}
function maxProfit(prices, k) {
  const n = prices.length;

  if (n === 0 || k === 0) {
    return 0;
  }

  const dp = Array.from({ length: n }, () =>
    Array.from({ length: k + 1 }, () => [0, 0])
  );

  // Holding a stock before any transaction.
  for (let t = 0; t <= k; t++) {
    dp[0][t][1] = -prices[0];
  }

  for (let day = 1; day < n; day++) {
    for (let t = 0; t <= k; t++) {
      // Do nothing.
      dp[day][t][0] = dp[day - 1][t][0];
      dp[day][t][1] = dp[day - 1][t][1];

      // Buy.
      dp[day][t][1] = Math.max(
        dp[day][t][1],
        dp[day - 1][t][0] - prices[day]
      );

      // Sell: completes one transaction.
      if (t > 0) {
        dp[day][t][0] = Math.max(
          dp[day][t][0],
          dp[day - 1][t - 1][1] + prices[day]
        );
      }
    }
  }

  return dp[n - 1][k][0];
}

For practical implementations, use the specialized O(1) or O(k) versions when the problem allows them.

8. Stock Span — Related but NOT DP

Stock Span is commonly grouped with stock questions, but it uses a completely different pattern.

The problem asks for:

How many consecutive previous prices are less than or equal to today’s price?

This is a Monotonic Stack problem.

Example

prices = [100, 80, 60, 70, 60, 75, 85]

span   = [1,   1,  1,  2,  1,  4,  6]

Why Not DP?

Stock DP asks:

What is the maximum profit?

Stock Span asks:

What previous elements can be removed efficiently?

That is exactly what a monotonic stack handles.

Java Template

class StockSpanner {

    private final Deque<int[]> stack = new ArrayDeque<>();

    public int next(int price) {
        int span = 1;

        while (!stack.isEmpty() &&
               stack.peek()[0] <= price) {

            span += stack.pop()[1];
        }

        stack.push(new int[]{price, span});

        return span;
    }
}
class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append((price, span))

        return span
class StockSpanner {
private:
    stack<pair<int, int>> st;

public:
    int next(int price) {
        int span = 1;

        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }

        st.push({price, span});

        return span;
    }
};
class StockSpanner {
  constructor() {
    this.stack = [];
  }

  next(price) {
    let span = 1;

    while (
      this.stack.length > 0 &&
      this.stack[this.stack.length - 1][0] <= price
    ) {
      span += this.stack.pop()[1];
    }

    this.stack.push([price, span]);

    return span;
  }
}

Complexity

Time:  O(n) amortized
Space: O(n)

Mental Trigger

“Consecutive previous smaller/equal prices” → Monotonic Stack

How the Stock Patterns Differ

The easiest way to distinguish stock problems is to ask:

1. How many transactions?

Stock Buy & Sell (DP)

Two classic DP framings of max-profit stock trading — one trade vs unlimited trades.

Track the lowest price seen so far and the best profit it enables: best = max(best, p − minPrice). One pass, O(n) time, O(1) space.

ARRAY VISUALIZER
Steps –
7
0
1
1
5
2
3
3
6
4
4
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        minPrice = +inf
                      
                        2
                        best = 0
                      
                        3
                        for p in prices:
                      
                        4
                          minPrice = min(minPrice, p)
                      
                        5
                          best = max(best, p - minPrice)
                      
                        6
                        return best
                      
One
→ Stock I

Unlimited
→ Stock II

Exactly/at most 2
→ Stock III

At most K
→ Stock IV

2. Is there a cooldown?

Yes
→ Add cooldown state

No
→ Normal hold/cash states

3. Is there a transaction fee?

Yes
→ Modify buy/sell transition

No
→ Normal transition

4. Is the question actually about profit?

Maximum profit
→ Stock DP

Previous smaller prices / consecutive span
→ Monotonic Stack

Comparison of Stock DP Patterns

ProblemStatesMain DifferenceSpace
Stock IminPrice, profitOne transactionO(1)
Stock IIhold, cashUnlimited tradesO(1)
Stock IIIbuy1, sell1, buy2, sell2At most 2 tradesO(1)
Stock IVtransaction × holdingAt most K tradesO(k)
Cooldownhold, sold, restWaiting after sellO(1)
Feehold, cashCost on transactionO(1)
Stock SpanStackNot a DP problemO(n)

How to Identify Stock DP

Ask these questions:

Question 1

Is the input a sequence of prices?

prices[i]

Question 2

Are you maximizing trading profit?

Question 3

Can you perform:

BUY
SELL
BUY
SELL
...

Question 4

Are there additional constraints?

number of transactions
cooldown
transaction fee

If yes:

Think Stock State Machine DP.

Common State Diagrams

Unlimited Transactions

             buy
        ┌────────────┐
        ↓            │
      cash ───────→ hold
        ↑            │
        └─── sell ───┘

Conceptually:

cash → hold → cash
       buy     sell

Cooldown

rest
 ↓ buy
hold
 ↓ sell
sold
 ↓ cooldown
rest

The important restriction is:

sold ──X──→ hold

You must first return to rest.

K Transactions

cash(t)
  ↓ buy
hold(t)
  ↓ sell
cash(t + 1)

Each completed:

BUY → SELL

uses one transaction.

Common Mistakes

Mistake 1: Allowing multiple stocks

This is usually not allowed.

The state machine assumes:

0 or 1 stock

not:

0, 1, 2, 3... stocks

Mistake 2: Counting BUY as a completed transaction

A transaction is normally completed on:

SELL

So for at-most-K problems, the transaction count is naturally associated with the sell operation.

Mistake 3: Updating states in the wrong order

When using previous states, avoid accidentally using values updated earlier on the same day.

A safe approach is:

int newHold = ...;
int newCash = ...;

hold = newHold;
cash = newCash;

Mistake 4: Forgetting the cooldown

For cooldown problems:

sold → hold

is invalid on the next day.

Mistake 5: Using DP for Stock Span

Stock Span is:

Monotonic Stack

not:

Stock DP

Universal Recognition Cheat Sheet

If you see…Think…
Buy once + sell onceMinimum Price Tracking
Unlimited buy/sellHold/Cash DP
At most 2 transactionsFour-State DP
At most K transactionsTransaction DP
Cannot buy after sellingCooldown DP
Transaction feeModified Hold/Cash
Previous smaller/equal pricesMonotonic Stack

Stock DP Decision Tree

                Stock Problem
                      │
                      ▼
              Maximum Profit?
                 /        \
               No          Yes
               │            │
               ▼            ▼
        Maybe Stack/      How many
        another pattern   transactions?
                           │
              ┌────────────┼────────────┐
              │            │            │
             One       Unlimited        K
              │            │            │
              ▼            ▼            ▼
          Stock I      Hold/Cash    Transaction DP
                                           │
                              ┌────────────┴───────────┐
                              │                        │
                         Cooldown?                  Fee?
                              │                        │
                              ▼                        ▼
                       Add state                Modify transition

My Private Notes

Notes are auto-saved locally to this device.