leetcode 714 股票手续费问题

使用动态规划方法，dp数组的状态和之前多次买卖的状态数量一样，一种是天数，一种是持有还是不持有，当股票卖出（买入也可以）需要减去手续费用，注意这个手续费用只能计算一次。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:

        dp=[[0,0]  for _ in range(len(prices))]
        dp[0][0]=0
        dp[0][1]=-prices[0]
        for i in range(1,len(prices)):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

        return dp[len(prices)-1][0]

空间优化

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:


        sell=0
        buy=-prices[0]
        for i in range(1,len(prices)):
            buy=max(buy,sell-prices[i])

            sell=max(sell,buy+prices[i]-fee)


        return sell