leetcode：714. 买卖股票的最佳时机含手续费【dp双状态】

分析

dp[i][0]表示第i个位置没股票max利润，dp[i][1]表示第i个位置有股票max利润
第0个的dp就是[0, -prices[0]]
然后dp[i][0]是max（之前没有股票的延续，之前有股票但卖了）
然后dp[i][1]是max（之前有股票的延续，之前没有股票但买了）

ac code

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # dp[i][0]: 第i天没有股票的最大利润
        # dp[i][1]: 第i天有股票的最大利润
        # 双状态
        n = len(prices)
        dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]

        for i in range(1, n):
            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[-1][0]

总结

dp双状态
互相影响
又是一个dp多状态，行吧