109. Leetcode 309. 最佳买卖股票时机含冷冻期 (动态规划-股票交易)

步骤一、确定状态:

确定dp数组及下标含义

dp[i]表示的是到第i天能获得的利润，但这里每天的状态下就不仅仅是持股和不 持股两种状态了，而是持股， 不持股当天卖出和不持股当天没卖出三种状态， 因为冷冻期的意思是如果昨天卖出了，今天不可以买入，所以持股的时候如果今 天买入，那么昨天肯定没有卖出，即必须要分析不持股是不是因为当天卖出了。 dp[i][0]表示不持有股票且不是当天没卖出， dp[i][1]表示持有股票， dp[i][2] 表示不持有股票但是是因为当天卖出的

首未持有股票的两种情况

1. 不是当天卖出的未持有股票 dp[i][0]， 这说明有可能是今天冷冻期，我昨 天卖的dp[i-1][2]， 也有可能是延续的之前的状态dp[i-1][0]。 我们选择 最大值，即dp[i][0]=max(dp[i-1][2], dp[i-1][0])

2. 由于今天卖了导致未持有股票dp[i][2], 那么就非常简单了，最大利润是 dp[i][2]=dp[i-1][1]+prices[i], 昨天一定是持有股票的

持有股票的一种情况， 也就是买入， 这时候和上面的II是一样的，要么是延 续的之前的状态dp[i-1][1]，之前买的，要么是今天买的，但这时候昨天一定 没有卖出股票， 否则就是冷冻期了， 所以这时候是dp[i-1][0]-prices[i]， 这 时候dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])

步骤三、规定初始条件:

初始条件:

全局初始化0， 局部初始化dp[0][0]=0,

dp[0][1]=-prices[0], dp[0][2]=float("inf") 这种 情况不可能

步骤四、计算顺序:

遍历方式会是从1开始遍历，正向， 最终返回的是未持股状态的 最大值

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0# dp[i][0] 表示不持有股票且不是当天卖出的# dp[i][1] 表示持有股票# dp[i][2] 表示不持有股票是当天卖出的dp = [[0 for _ in range(3)] for _ in range(len(prices))]dp[0][0] = 0dp[0][1] = -prices[0]dp[0][2] = float("-inf")for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0],dp[i-1][2])dp[i][2] = dp[i-1][1] + prices[i]dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])return max(dp[-1][0],dp[-1][2])

总结

以上是生活随笔为你收集整理的109. Leetcode 309. 最佳买卖股票时机含冷冻期 (动态规划-股票交易)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。