?

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

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

dp[i] 表示的是在第i天可以獲取的最大利潤，每天會有持有股票和不持有股票兩種狀態(tài)，這個是 第二維度，還是用0和1表示。 而對于每一種狀態(tài)，這里還會有交易次數(shù)的記錄0次or1次or2次， 這個是第三維度。所以dp[天數(shù)][當(dāng)前是否持股][賣出的次數(shù)]

步驟二、推斷狀態(tài)方程:

dp[i][0]，也就是沒有持股的狀態(tài)，會有三次交易次數(shù)討論:

dp[i][0][0]: 表示的是當(dāng)前未持股， 且交易了0次，說明目前是從未進(jìn)行買賣， 那么此時最 大利潤為 dp[i][0][0]=0

dp[i][0][1]: 表示的是當(dāng)前未持股，且有1次交易時最大利潤，賣出過1次股票，在第1次賣 出的狀態(tài)，那么它的狀態(tài)依然來自兩個方向推導(dǎo)過來的，可能是今天賣出去的，也可能是 延續(xù)了昨天的狀態(tài):

如果是延續(xù)了昨天的狀態(tài)， 那么最大利潤就是dp[i-1][0][1]

如果是今天剛賣出去的， 說明昨天是持有股票的，也就是昨天沒有賣出(之前交易了0次)， 那么最大利潤就是dp[i-1][1][0]+prices[i]

所以這時候要選最大， dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])

dp[i][0][2]: 表示的是當(dāng)前未持股， 且有2次交易股票時最大利潤，這是第二次賣出的狀 態(tài)，狀態(tài)依然是兩個方向推導(dǎo)過來，可能是今天賣出去的，也可能延續(xù)了前面的狀態(tài):

如果是延續(xù)了昨天的狀態(tài)， 那么最大利潤就是dp[i-1][0][2]

如果是今天剛賣出去的， 說明昨天是持有股票的，但是此時已經(jīng)交易過了1次了，那么 最大利潤就是dp[i-1][1][1]+prices[i]

所以這時候要選最大， dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])

然后是dp[i][1]， 也就是持股狀態(tài)，依然會有三次次交易討論:

dp[i][1][0]: 表示的是當(dāng)前持股，且有0次股票交易時的利潤，也就是第一次買入的狀態(tài)， 那么它的狀 態(tài)依然來自兩個方向推導(dǎo)過來的，可能是今天剛買的，也可能是延續(xù)了昨天的狀態(tài)如果是延續(xù)了昨天 的狀態(tài)， 那么最大利潤就是dp[i-1][1][0]

如果是今天剛買的， 說明昨天是沒有股票的，那么最大利潤就是dp[i-1][0][0]-prices[i] 所以這時候要選最大， dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])

dp[i][1][1]: 表示的是當(dāng)前持股，且有1次股票交易時的利潤，也就是第二次買入的狀態(tài)，那么它的狀 態(tài)依然來自兩個方向推導(dǎo)過來的，可能是今天剛買的，也可能是延續(xù)了昨天的狀態(tài)如果是延續(xù)了昨天 的狀態(tài)， 那么最大利潤就是dp[i-1][1][1]

如果是今天剛買的， 說明昨天是沒有股票的，那么最大利潤就是dp[i-1][0][1]-prices[i] 所以這時候要選最大， dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])

dp[i][1][2]: 表示的是當(dāng)前持股， 且有2次股票交易時的利潤，這個情況是不可能出現(xiàn)的，因為進(jìn)行 完兩筆交易就不能交易了呀，這時候可以給個最小的負(fù)數(shù)即可。

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

初始條件:

全局初始化為0， 然后第0天的所有狀態(tài)必須都初始化出來: dp[0][0][0] = 0: 開始啥也沒干， 利潤0

dp[0][0][1] = float("-inf"): 第0天沒有持有股票，且進(jìn)行了一次交易，這種情況不 可能

dp[0][0][2] = float("-inf"):第0天沒有持有股票，且進(jìn)行了兩次交易，這種情況依 然不可能

dp[0][1][0] = -prices[0]: 第0天持有股票，且進(jìn)行了0次交易，這是第一次買入，利 潤-prices[0]

dp[0][1][1] = float("-inf"): 第0天持有股票，且進(jìn)行了1次交易，這種情況不可能 dp[0][1][2] = float("-inf"): 第0天持有股票，且進(jìn)行了2次交易，這種情況不可能

class Solution:def maxProfit(self, prices: List[int]) -> int:# 異常判斷if len(prices) == 1:return 0# dp[天數(shù)][當(dāng)天是否持股][賣出的次數(shù)] 最大利潤# 當(dāng)天是否持股: 0 or 1# 賣出的次數(shù): 0、1、2dp = [[[0 for _ in range(3)] for _ in range(2)] for _ in range(len(prices))]dp[0][0][0], dp[0][0][1], dp[0][0][2] = 0, float("-inf"), float("-inf")dp[0][1][0], dp[0][1][1], dp[0][1][2] = -prices[0], float("-inf"), float("-inf")for i in range(1, len(prices)):# 不持有股票dp[i][0][0] = 0dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i]) # 第一次賣出dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i]) # 第二次賣出# 持有股票dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i]) # 第一次買入dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i]) # 第二次買入dp[i][1][2] = float("inf") # 第三次買入不可能# 返回最后一天未持有股票的值return max(dp[-1][0])

總結(jié)

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

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