Shouyu

Appearance

股票问题总结 ​

这几个股票问题有一些共性，先贴出来。

核心要点 ​

  1. 状态设计统一模式：

    • dp[i][k][0/1] 表示第i天最多k次交易时的持有状态
    • 通常可简化为dp[i][0/1]（当k固定或无限时）

  2. 关键状态转移方程：

    • 持有状态：dp[i][1] = max(保持持有, 当天买入)
    • 非持有状态：dp[i][0] = max(保持不持有, 当天卖出)

  3. 典型变种处理：

    • 单次交易(121)：k=1
    • 无限交易(122)：k可忽略
    • 两次交易(123)：k=2
    • 含冷冻期(309)：卖出后需跳过一天
    • 含手续费(714)：卖出时扣除fee

  4. 初始化要点：

    • dp[0][1] = -prices[0]（首日买入）
    • 其他状态根据问题约束初始化

  5. 时间效率：

    • 基本形式：O(n)
    • 限制k次交易：O(n∗k)

买卖股票的最佳时机（单次交易） ​

  • 特点：只能买卖一次
  • 贪心解法：记录历史最低价，计算每日最大利润
  • 动规解法：持有与不持有两种状态，取最大值
C++
dp[i][0] = max(dp[i - 1][0],-prices[i]);
dp[i][1] = max(dp[i - 1][1],prices[i] + dp[i - 1][0]);

买卖股票的最佳时机 II（无限交易） ​

  • 特点：可多次买卖
  • 贪心解法：所有上涨日都交易
  • 动规解法：持有与不持有两种状态，取最大值；与 问题 I 唯一不同的是第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。因此设置为dp[i - 1][1] - prices[i]
C++
dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]-prices[i]);
dp[i][1] = max(dp[i - 1][1],prices[i] + dp[i - 1][0]);

买卖股票的最佳时机 III（两次交易） ​

  • 特点：最多两次买卖
  • 解法：5种状态D：没有操作、第一次买入、第一次卖出、第二次买入、第二次卖出
C++
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

买卖股票的最佳时机 IV（k次交易） ​

  • 特点：最多k次买卖
  • 解法：2k+1 种状态DP
C++
dp[i][j+1] = max(dp[i - 1][j+1], dp[i - 1][j] - prices[i]);
dp[i][j+2] = max(dp[i - 1][j+2], dp[i - 1][j+1] + prices[i]);

最佳买卖股票时机含冷冻期 ​

  • 特点：卖出后需冷却1天
  • 解法：4种状态DP：
    • 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
    • 卖出股票状态，这里就有两种卖出股票状态
      • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
      • 状态三：今天卖出了股票
    • 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
C++
dp[i][0] = max(dp[i - 1][0],max(dp[i - 1][1] - prices[i],dp[i - 1][3] - prices[i]));
dp[i][1] = max(dp[i - 1][1],dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];

买卖股票的最佳时机含手续费 ​

  • 特点：每笔交易扣手续费
  • 解法：DP或贪心（调整买入价）
C++
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);