跳到主要内容

买卖股票的最佳时机

为什么股票问题适合用状态机描述？​

  • 问题: 最多完成两次交易, 求最大利润 (123);
  • 原因: 每天的结果不只取决于价格, 还取决于"当前持有几次交易的什么状态";
  • 结论: 把"是否持股、已完成几次交易"作为状态的维度, 用状态机在每天之间迁移;

状态如何定义？​

  • 状态维度: dp[i][j] 表示区间 [0, i] 内、处于状态 j 时的最大收益;
  • 五种状态:
    • 0: 不进行任何操作;
    • 1: 第一次持有股票;
    • 2: 第一次不持有股票 (已完成第一次交易);
    • 3: 第二次持有股票;
    • 4: 第二次不持有股票 (已完成两次交易);
  • 初值: dp[0][0] = dp[0][2] = dp[0][4] = 0 (空仓无收益), dp[0][1] = dp[0][3] = -prices[0] (当天买入);
  • 答案: max(dp[n-1]), 即 dp[n-1][4];

状态之间如何迁移？​

目标状态不操作操作
0dp[i-1][0]无
1dp[i-1][1]买入: dp[i-1][0] - prices[i]
2dp[i-1][2]卖出: dp[i-1][1] + prices[i]
3dp[i-1][3]买入: dp[i-1][2] - prices[i]
4dp[i-1][4]卖出: dp[i-1][3] + prices[i]
  • 统一形式: 每个状态取"保持不变"和"由前一状态转移"的较大值;
const maxProfit = (prices) => {
  const n = prices.length;
  const dp = Array.from({ length: n }, () => new Array(5).fill(0));
  dp[0][1] = dp[0][3] = -prices[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0];
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
    dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
    dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
  }
  return Math.max(...dp[n - 1]);
};
  • 复杂度: 时间 O(n), 空间 O(n * k), k 为状态数;

交易次数变化时如何扩展？​

  • 一次交易: 保留状态 0/1/2;
  • 两次交易: 扩展到 0/1/2/3/4;
  • k 次交易: 状态数变为 2k + 1, 每天对每个状态做一次"不动或迁移"的比较;
  • 也可压缩: 用买入/卖出两个滚动变量按交易轮次迭代, 空间降到 O(k);