做网站的服务商,网站服务器配置,建外文网站,网站建设哪家企业好文章目录 309. 最佳买卖股票时机含冷冻期标准 dp机智的分析解法 714. 买卖股票的最佳时机含手续费贪心算法 股票总结 309. 最佳买卖股票时机含冷冻期
题目链接 | 解题思路
标准 dp
本题多了冷却期的条件#xff0c;将原本的两个状态变得更复杂了。变化在于#xff0c;如果… 文章目录 309. 最佳买卖股票时机含冷冻期标准 dp机智的分析解法 714. 买卖股票的最佳时机含手续费贪心算法 股票总结 309. 最佳买卖股票时机含冷冻期
题目链接 | 解题思路
标准 dp
本题多了冷却期的条件将原本的两个状态变得更复杂了。变化在于如果考虑第 i 天的状态是“持有股票”那么不能简单地推导为“第 i-1 天持有股票”和“第 i-1 天未持有股票第 i 天买入股票”因为可能第 i 天是冷却期。所以需要特殊讨论针对冷却期的递推公式。
可以看到和之前的一个最大的区别在于本题需要详细地分类讨论“不持有股票的状态”。每一天的情况可能是“持有股票”“未持有股票 不在冷却期”“未持有股票 在冷却期”“未持有股票 刚卖出股票”。分类讨论的情况更多了需要更清晰的递推公式。另外本题还单独列出了“今天刚卖出股票”这个具体的动作状态是因为“刚卖出股票” - “冷却期”这个递推是确定的。
dp 数组的下标含义 dp[i][0]第 i 天结束时持有股票dp[i][1]第 i 天结束时不持有股票 不在冷却期内dp[i][2]第 i 天结束时不持有股票 当天卖出股票dp[i][3]第 i 天结束时不持有股票 当天为冷却期 dp 递推公式 dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - prices[i])如果第 i 天持有股票那么 第 i-1 天就持有股票dp[i][0] dp[i-1][0]第 i-1 天不持有股票那又分为两种情况 第 i-1 天是冷却期第 i 天可以正常交易dp[i][0] dp[i-1][3]第 i-1 天不在冷却期内第 i 天可以正常交易dp[i][0] dp[i-1][1] dp[i][1] max(dp[i-1][1], dp[i-1][3])如果第 i 天不是冷却期那么 第 i-1 天就不在冷却期dp[i][1] dp[i-1][1]第 i-1 天就是冷却期dp[i][1] dp[i-1][3] dp[i][2] dp[i-1][0] prices[i]如果第 i 天要卖出股票那么第 i-1 天必然是持有股票的dp[i][3] dp[i-1][2]如果第 i 天是冷却期那么第 i-1 天必然是卖出股票的 dp 数组的初始化初始化自然是考虑第一天本题的初始化还是有些难判断的 dp[0][0] -prices[0]显然第一天结束时持有股票那只能是第一天购买了股票dp[0][1] 0显然第一天结束时没有持有股票只能是第一天没有任何操作dp[0][2] 0符合定义的话只能是第一天就买入再卖出股票收益为 0dp[0][3] 0根据定义这个状态是非法的因为很明显不可能在第一天就进入冷却期没有办法在前一天卖出股票。然而定义上非法的初始化也要为了后续的递推服务所以可以根据递推公式来得到初始化的值 在第二天的状态中只有 dp[1][1] max(dp[0][1], dp[0][3]) 会用到 dp[0][3]。从含义上第二天如果不持有股票并且不在冷却期那么第一天就肯定没有买入股票dp[1][1] 应该是 0dp[0][1]。那么为了得到正确的 dp[1][1]我们应该初始化 dp[0][3] 0。 dp 的遍历顺序从前向后即可。举例推导
123020-1-1-1111000122012-1330012-1
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 1:return 0dp [[0] * 4 for _ in range(len(prices))]dp[0][0] -prices[0]for i in range(1, len(prices)):dp[i][0] max(dp[i-1][0], 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]return max(dp[-1][1], dp[-1][2], dp[-1][3])和之前一样也可以优化成 O ( 1 ) O(1) O(1) 的空间复杂度。
机智的分析解法
本题和122. 买卖股票的最佳时机II的区别只在于多了一个冷却期。如上的状态分析是解决题目的标准流程。但是延续之前题目的做法同样也能解决这道题。注意到不持有股票的状态不会受到任何影响只有想要买入股票的时候需要考虑冷却期的存在。
关键在于“如果第 i 天持有股票那么当前的收益究竟怎么进行推导”
如果第 i - 1 天就持有股票那么就直接复制前一天的状态dp[i][1] dp[i-1][1]如果第 i - 1 天未持有股票那么分两种情况 第 i - 1 天是冷却期那么就是在第 i - 2 天卖出了股票dp[i][1] dp[i-2][0] - prices[i]第 i - 1 天不是冷却期那么应该得到 dp[i][1] dp[i-1][0] - prices[i]
如果根据以上的状态分析无法得到一个 closed-form 的递推公式因为我们不知道第 i-1 天是否是冷却期也就不知道何时该使用 dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])何时该使用 dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])。 但是如果第 i-1 天不是冷却期且不持有股票那么第 i-1 天只有两种情况
之前从来没有交易过股票第 i - 2 天或之前是冷却期
无论是哪种情况我们都能得到 dp[i-1][0] dp[i-2][0]。所以虽然第 i-1 天的状态是否是冷却期不得而知但是第 i 天持有股票的递推公式可以确定是 dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])。
这样我们只需要最小限度地修改122. 买卖股票的最佳时机II的代码就能解题。
class Solution:def maxProfit(self, prices: List[int]) - int:if len(prices) 1:return 0# dp[i][0] represents the max profit on day i without the stock# dp[i][1] represents the max profit on day i with the stockdp [[0, 0] for _ in range(len(prices))]dp[0] [0, -prices[0]]dp[1] [max(0, prices[1] - prices[0]), max(-prices[0], -prices[1])]for i in range(2, len(prices)):dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i])dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])return dp[-1][0]714. 买卖股票的最佳时机含手续费
题目链接 | 解题思路
本题的 dp 解法和122. 买卖股票的最佳时机II唯一的区别是多了一个手续费所以从“持有股票”到“未持有股票”的利润递推需要多减去手续费其他全部保持不变。
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:# dp[i][0] represents the max profit on day i without the stock# dp[i][1] represents the max profit on day i with the stockdp [[0, 0] for _ in range(len(prices))]dp[0] [0, -prices[0]]for i in range(1, len(prices)):dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i] - fee)dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])return dp[-1][0]贪心算法
贪心解法 本题也可以用贪心算法来解决也算是照应了122. 买卖股票的最佳时机II。但是本题的贪心解法不像之前一样简单在计算的时候对所需要的区间要求更高情况也更复杂。
如果简单计算所有增区间那么就会遇到有的区间利润不足以抵手续费的情况同时多次买卖也会导致更多的手续费从而使利润降低。所以我们想找到的区间应该是
买入利润遇到更低的价格就更新记录卖出利润按理来说是当前增最大区间的最后一天的利润。但是没必要具体知道哪一天进行了卖出只要当能够盈利的时候进行一次模拟的卖出即可同样能够得到正确的利润但是需要一些小技巧。
如下在第一次发现当前的交易能够制造利润时prices[i] min_price fee我们会选择直接进行当前交易并且扣除一次手续费随后减少 min_price。之后会有两种情况假设 fee 2,
prices [1, 4, 0, 5] 第二天发现有真正的盈利profit 1, min_price 2第三天发现了更低的价格min_price 0将会开始新的交易同时结束了上一次的交易记录区间 prices [1, 5, 8] 第二天发现有真正的盈利profit 2, min_price 3第三天发现有真正的盈利此时新的盈利为5而不是预计的3因为 min_price 在这次计算前发生了变化相当于抵消了该次交易的手续费
所以模拟的卖出实际上是在第一次发现真正的盈利后就记录一次交易的手续费并且改变当前的 min_price从而免除当前区间的后续交易如果存在的手续费。着实非常巧妙
class Solution:def maxProfit(self, prices: List[int], fee: int) - int:min_price prices[0]profit 0for i in range(1, len(prices)):if prices[i] min_price:min_price prices[i]if prices[i] prices[i] min_price fee:continueif prices[i] min_price fee:profit (prices[i] - min_price) - feemin_price prices[i] - feereturn profit股票总结
股票问题总结
股票问题是第一次在 dp 中需要记录状态的题型。之前的 dp 题无论是打家劫舍还是背包问题都是考验对子问题最优解的利用即正确的递推公式遍历顺序。股票问题则需要对子问题进行分类讨论记录各个状态下的子问题最优解这一点是非常新颖的。同时不知道是不是巧合大部分股票问题都可以用贪心来解决虽然实现贪心的难度不小。
最标准的股票问题应该是122. 买卖股票的最佳时机II需要真正地记录并利用状态。
随后复杂的限制交易次数的股票问题188.买卖股票的最佳时机IV把 dp 变得更复杂了相比于之前的标准题有了类似爬楼梯式的进阶。
而堪称神题的是309.最佳买卖股票时机含冷冻期。标准解法中活用了状态分类的思想将原本的“未持有股票”进一步细分来适应新条件下的递推公式。而机智的分析算法中通过分析最小限度地修改了之前的代码解决了问题。两种解法都非常重要代表了股票问题的精华。
