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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

解法一：状态机dp

k 为正无穷，参考122. 买卖股票的最佳时机，只是多了手续费的条件，状态方程变为

0 ≤ i ≤ n-1
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])
解释：手续费在状态0时计算和1时是等效的，分别对应买时收费和卖时收费，只影响dp[i][1]的结果
我们最后求的是dp[n-1][0]

初始条件：

dp[0][0] = 0, dp[0][1] = -∞

直接出代码：

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n+1)]
        for i in range(n+1):
            if i == 0:
                dp[0][0] = 0
                dp[0][1] = -sys.maxsize
                continue
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1] - fee)
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])
        return dp[n][0]