LeetCode-714-买卖股票的最佳时机含手续费

image.png

解题思路：

第i天持有股票dp_1[i]的最大收益由两个状态转移而来，昨天持有股票or昨天没有持有股票但今天买入了，求两个状态的收益最大值 dp_1[i] = max(dp_1[i-1], dp_0[i-1]-prices[i])
第i天没有持有股票dp_0[i]的最大收益，由两个状态转移而来，昨天没有持有or昨天持有，今天卖出了，求两个状态的收益最大值dp_0[i] = max(dp_0[i-1], dp_1[i-1]+prices[i]-fee)
初始状态: 第一天不持有股票，收益为0：dp_0[0]=0，第一天持有股票，收益为负值，因为买入了当天的股票：dp_1[1]=-prices[0]
最后一天不持有股票，得出最大的收益dp_0[-1]

python3代码如下：

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp_0 = [0] * len(prices) 
        dp_1 = [0] * len(prices)
        dp_0[0] = 0
        dp_1[0] = -prices[0]
        for i in range(1, len(prices)):
            dp_0[i] = max(dp_0[i-1], dp_1[i-1]+prices[i]-fee)
            dp_1[i] = max(dp_1[i-1], dp_0[i-1] - prices[i])
        return dp_0[-1]