步驟一、確定狀態:

確定dp數組及下標含義 dp[i]是一個長度為len(prices)的一維數組，表示的是在第i天持有股票

步驟二、推斷狀態方程:

第i天不持有股票，即dp[i][0], 那么兩個狀態:

不持有股票是延續了昨天的， 那么dp[i][0] = dp[i-1][0]

不持有股票是因為今天剛賣出,此時要拿手續費, dp[i][0]=dp[i- 1][1]+prices[i]-fee

這時候選最大的dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]-fee)， 其 他的都和II保持一樣，

第i天持有股票，即dp[i][1], 那么兩個狀態:

1、第i-1天就持有股票， 保持現狀過來的， 最大利潤就是昨天持有股票的最 大利潤dp[i-1][1]

2、第i-1天沒有股票，第i天剛買進來的， 那這時候的最大利潤就是dp[i- 1][0]-prices[i]，注意這個不是僅僅的-prices[i]了， 因為此時可以進行多次 交易了， 即使第i-1沒有股票，那么也可能會有更前面的利潤傳過來，dp[i][1] 選擇最大的: dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])

步驟三、規定初始條件:

初始條件:

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

步驟四、計算順序:

從左往右， 從1開始遍歷，返回的是最后沒有股票時候的最大利潤， 也就是dp[-1][0]

class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:if len(prices) <= 1:return 0dp = [[0 for _ in range(2)] for _ in range(len(prices))]dp[0][0] = 0dp[0][1] = -prices[0]for i in range(1, len(prices)):# 第i天不持有股票dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)# 第i天持有股票dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])return dp[-1][0]

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。