Dynamic Programming Approaches for Stock Trading Problems: A Unified Framework

The labuladong/fucking-algorithm repository provides a unified dynamic programming framework that solves all stock trading variations using a three-dimensional state representation (day, remaining transactions k, holding status), which can be simplified to O(1) space for specific constraints like unlimited transactions, cooldown periods, or transaction fees.

The repository labuladong/fucking-algorithm offers a comprehensive guide to solving LeetCode stock trading problems through dynamic programming. By treating each day as a state transition and tracking whether you hold a stock or not, these approaches convert complex trading scenarios into manageable recurrence relations. The core framework is documented in 动态规划系列/团灭股票问题.md.

The Core DP Framework

At the heart of every stock trading solution lies a state machine with three dimensions: the current day i, the number of remaining transactions k, and a binary flag h indicating whether you currently hold a stock. This three-dimensional DP approach provides the general solution that can be adapted to any constraint.

State Definition

The DP array dp[i][k][h] represents the maximum profit achievable by day i with at most k transactions remaining and holding status h (where 0 means not holding, 1 means holding).

State Transitions

For each day, you have two choices depending on your current state:

1. If not holding (h=0): You either continue resting or sell the stock you held yesterday.

   
   dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
   

2. If holding (h=1): You either continue holding or buy today (consuming one transaction).

   
   dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
   

Specific Dynamic Programming Approaches

3D DP for Bounded Transactions

When the number of allowed transactions k is limited (LeetCode 188), you must track the remaining transaction count explicitly. The full three-dimensional array dp[n][k+1][2] provides the solution in O(n·k) time.

int maxProfit_k_any(int max_k, int[] prices) {
    int n = prices.length;
    if (max_k > n/2) return maxProfit_k_inf(prices); // unlimited case
    
    int[][][] dp = new int[n][max_k+1][2];
    for (int i = 0; i < n; ++i) {
        for (int k = max_k; k >= 1; --k) {
            if (i == 0) {
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        }
    }
    return dp[n-1][max_k][0];
}

Source: 动态规划系列/团灭股票问题.md in the labuladong/fucking-algorithm repository.

2D DP for Unlimited Transactions

When k is unlimited (LeetCode 122), the transaction count dimension becomes irrelevant. The state reduces to dp[i][h], simplifying to a two-dimensional problem where you buy whenever profitable.

int maxProfit_k_inf(int[] prices) {
    int cash = 0, hold = Integer.MIN_VALUE;
    for (int p : prices) {
        int prevCash = cash;
        cash = Math.max(cash, hold + p);
        hold = Math.max(hold, prevCash - p);
    }
    return cash;
}

Space-Optimized O(1) Solutions

Most stock problems only require the previous day's state. By replacing arrays with scalar variables (cash and hold), you achieve O(1) space complexity. This optimization applies to all variants including single transaction, unlimited transactions, cooldown, and fee scenarios.

Handling Cooldown Periods

For problems requiring a cooldown after selling (LeetCode 309), the buy transition looks back c+1 days instead of 1 day. With c = 1, you reference dp[i-2][k-1][0] when buying on day i.

int maxProfit_with_cool(int[] prices) {
    int n = prices.length;
    int cash = 0, hold = Integer.MIN_VALUE;
    int cashPrevPrev = 0;               // dp[i-2][0]
    for (int i = 0; i < n; ++i) {
        int prevCash = cash;
        cash = Math.max(cash, hold + prices[i]);
        hold = Math.max(hold, cashPrevPrev - prices[i]); // buy after cooldown
        cashPrevPrev = prevCash;
    }
    return cash;
}

Source: 动态规划系列/团灭股票问题.md – LeetCode 309 implementation.

Incorporating Transaction Fees

When each transaction incurs a fee (LeetCode 714), subtract the fee during the buy or sell operation. Typically, subtracting when buying simplifies the state transition: dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i] - fee).

int maxProfit_with_fee(int[] prices, int fee) {
    int cash = 0, hold = Integer.MIN_VALUE;
    for (int p : prices) {
        int prevCash = cash;
        cash = Math.max(cash, hold + p);
        hold = Math.max(hold, prevCash - p - fee);
    }
    return cash;
}

The All-in-One Implementation

The repository provides a comprehensive solution combining all constraints: bounded transactions k, cooldown c, and transaction fee fee. This implementation uses the full 3D DP structure with modified transitions to handle the additional restrictions.

int maxProfit_all_in_one(int max_k, int[] prices, int cooldown, int fee) {
    int n = prices.length;
    if (n == 0) return 0;
    if (max_k > n/2) return maxProfit_k_inf(prices); // fallback to unlimited

    int[][][] dp = new int[n][max_k+1][2];
    for (int i = 0; i < n; ++i) {
        for (int k = max_k; k >= 1; --k) {
            if (i == 0) {
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i] - fee;
                continue;
            }
            // Sell: no cooldown or fee impact
            dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            // Buy: respect cooldown and pay fee
            if (i - cooldown - 1 >= 0) {
                dp[i][k][1] = Math.max(dp[i-1][k][1],
                                      dp[i-cooldown-1][k-1][0] - prices[i] - fee);
            } else {
                dp[i][k][1] = Math.max(dp[i-1][k][1], -prices[i] - fee);
            }
        }
    }
    return dp[n-1][max_k][0];
}

Source: 动态规划系列/团灭股票问题.md – "All-in-One" section in the labuladong/fucking-algorithm repository.

Summary

• Unified Framework: All stock trading problems can be solved using a three-dimensional DP state dp[i][k][h] representing day, remaining transactions, and holding status.
• Dimensionality Reduction: When transaction limits are removed (k = ∞), the problem simplifies to 2D; when only previous states matter, it compresses to O(1) space using scalar variables.
• Constraint Handling: Cooldown periods modify the buy transition to look back c+1 days, while transaction fees adjust the cost basis during purchase or sale operations.
• Implementation Source: The complete solutions are documented in 动态规划系列/团灭股票问题.md within the labuladong/fucking-algorithm repository, providing both mathematical frameworks and optimized Java implementations.

Frequently Asked Questions

What is the time complexity of the general stock trading DP solution?

The general three-dimensional DP solution using states dp[i][k][2] runs in O(n·k) time where n is the number of days and k is the maximum allowed transactions. When k exceeds n/2, the algorithm switches to the O(n) unlimited transaction variant since you can trade every day. Space complexity is O(n·k) for the full table, but can be optimized to O(k) or O(1) when only previous day states are required.

How does the cooldown constraint modify the standard DP transition?

When a cooldown period of c days is enforced after selling, the buy transition cannot reference the previous day's cash state. Instead, it must look back c+1 days to dp[i-c-1][k-1][0]. For the common case where c = 1 (LeetCode 309), this means dp[i][k][1] = max(dp[i-1][k][1], dp[i-2][k-1][0] - prices[i]), ensuring you cannot buy immediately after selling.

Can the space complexity be reduced for all stock trading variants?

Yes, space optimization applies to all stock trading DP variants because each day's state depends only on the previous day. By replacing the dp[i] array with scalar variables—typically cash (not holding) and hold (holding)—you reduce space from O(n·k) or O(n) to O(1). This optimization works for single transactions, unlimited transactions, cooldown scenarios, and transaction fees, though the bounded k case requires O(k) space to track each transaction limit separately.

Where can I find the complete implementation of the all-in-one stock trading solution?

The comprehensive implementation combining bounded transactions (k), cooldown (c), and transaction fees (fee) is located in the file 动态规划系列/团灭股票问题.md within the labuladong/fucking-algorithm repository. This document provides the complete Java code for the maxProfit_all_in_one function, along with detailed explanations of how each constraint modifies the base DP transitions. The repository also contains individual solutions for specific LeetCode problems (121, 122, 309, 714, 188) in the same file.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}