股票问题总结

股票问题总结

Zhou Shouyu
#算法笔记 #动态规划 #股票问题 #状态机 #算法总结
Table of Contents

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

核心要点

  1. 状态设计统一模式：

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

  1. 关键状态转移方程：

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

  1. 典型变种处理：

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

  1. 初始化要点：

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

  1. 时间效率：

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

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

  • 特点：只能买卖一次

  • 贪心解法：记录历史最低价，计算每日最大利润

  • 动规解法：持有与不持有两种状态，取最大值

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]

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：没有操作、第一次买入、第一次卖出、第二次买入、第二次卖出

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

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：

状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作） 卖出股票状态，这里就有两种卖出股票状态

状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态 状态三：今天卖出了股票

状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

  • 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）

  • 卖出股票状态，这里就有两种卖出股票状态

状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态 状态三：今天卖出了股票

  • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态

  • 状态三：今天卖出了股票

  • 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

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或贪心（调整买入价）

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);
Avatar