步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義

dp[i]表示的是到第i天能獲得的利潤，但這里每天的狀態(tài)下就不僅僅是持股和不 持股兩種狀態(tài)了，而是持股， 不持股當(dāng)天賣出和不持股當(dāng)天沒賣出三種狀態(tài)， 因為冷凍期的意思是如果昨天賣出了，今天不可以買入，所以持股的時候如果今 天買入，那么昨天肯定沒有賣出，即必須要分析不持股是不是因為當(dāng)天賣出了。 dp[i][0]表示不持有股票且不是當(dāng)天沒賣出， dp[i][1]表示持有股票， dp[i][2] 表示不持有股票但是是因為當(dāng)天賣出的

首未持有股票的兩種情況

1. 不是當(dāng)天賣出的未持有股票 dp[i][0]， 這說明有可能是今天冷凍期，我昨 天賣的dp[i-1][2]， 也有可能是延續(xù)的之前的狀態(tài)dp[i-1][0]。 我們選擇 最大值，即dp[i][0]=max(dp[i-1][2], dp[i-1][0])

2. 由于今天賣了導(dǎo)致未持有股票dp[i][2], 那么就非常簡單了，最大利潤是 dp[i][2]=dp[i-1][1]+prices[i], 昨天一定是持有股票的

持有股票的一種情況， 也就是買入， 這時候和上面的II是一樣的，要么是延 續(xù)的之前的狀態(tài)dp[i-1][1]，之前買的，要么是今天買的，但這時候昨天一定 沒有賣出股票， 否則就是冷凍期了， 所以這時候是dp[i-1][0]-prices[i]， 這 時候dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])

步驟三、規(guī)定初始條件:

初始條件:

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

dp[0][1]=-prices[0], dp[0][2]=float("inf") 這種 情況不可能

步驟四、計算順序:

遍歷方式會是從1開始遍歷，正向， 最終返回的是未持股狀態(tài)的 最大值

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0# dp[i][0] 表示不持有股票且不是當(dāng)天賣出的# dp[i][1] 表示持有股票# dp[i][2] 表示不持有股票是當(dāng)天賣出的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])

總結(jié)

以上是生活随笔為你收集整理的109. Leetcode 309. 最佳买卖股票时机含冷冻期 (动态规划-股票交易)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。