跳到主要内容

买卖股票系列问题

股票买卖系列是一类经典的动态规划问题，它们的状态通常包含：天数、是否持有股票、剩余交易次数。

通用状态定义​

dp[i][k][0] 表示在第 i 天，最多进行过 k 次交易，且当天手中不持有股票时的最大收益。 dp[i][k][1] 表示在第 i 天，最多进行过 k 次交易，且当天手中持有股票时的最大收益。

状态转移图​

状态转移方程​

  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) (买入或保持持有)

空间优化思路​

由于第 i 天的状态仅由 i-1 天决定，我们可以使用变量压缩空间。对于最常用的 不限次数交易 (LeetCode 122)：

int sold = 0, hold = -prices[0];
for (int i = 1; i < n; i++) {
    int nextSold = Math.max(sold, hold + prices[i]);
    int nextHold = Math.max(hold, sold - prices[i]);
    sold = nextSold;
    hold = nextHold;
}

这种技巧在面试中极为常见。

典型问题​

1. 只能交易一次 (LeetCode 121)​

相当于 k = 1。

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

2. 可以交易多次 (LeetCode 122)​

相当于 k = +infinity。只需记录每天不持有(sold)和持有(hold)的状态。

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        // 如果明天价格涨了，今天就买明天卖
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

3. 最多交易两次 (LeetCode 123)​

相当于 k = 2。

public int maxProfit(int[] prices) {
    int n = prices.length;
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    for (int i = 1; i < n; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
}

4. 最多交易 k 次 (LeetCode 188)​

使用数组记录 k 个买入/卖出状态。

5. 含冷冻期 (LeetCode 309)​

卖出后必须休息一天才能买。

练习​

  1. LeetCode 121：买卖股票的最佳时机
  2. LeetCode 122：买卖股票的最佳时机 II
  3. LeetCode 123：买卖股票的最佳时机 III
  4. LeetCode 188：买卖股票的最佳时机 IV
  5. LeetCode 309：最佳买卖股票时机含冷冻期
  6. LeetCode 714：买卖股票的最佳时机含手续费
  7. 理解 股票问题通用解法。