买卖股票的最佳时机含手续费
题目描述：
题目分析：
1. 状态分析
其实一共就只有两种状态，不是处于 持有 状态，就是处于 未持有 状态。
- f[i] 表示第 i 天结束后，处于 持有 状态时，最大的利润
- g[i] 表示第 i 天结束后，处于 未持有 状态时，最大的利润
2. 状态转移方程
对于 f[i]，有两种情况可以到达这种状态:
- 在第 i-1 天时就已处于 持有 状态，然后第 i 天啥也不干，仍然保持 持有 状态。此时的最大利润就为 f[i - 1]
- 在 i - 1 天的时候「未持有」股票，在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i]
可知 f[i] 就为以上两种情况下的最大值，即
f[i] = max(f[i - 1], g[i - 1] - prices[i])
对于 g[i]，也有两种情况能够到达这种状态：
- 在 i - 1 天「持有」股票，但是在第 i 天将股票卖出。此时最⼤收益为： f[i - 1] + prices[i] - fee)，记得⼿续费
- 在 i - 1 天「未持有」股票，然后第 i 天啥也不⼲。此时最⼤收益为： g[i - 1]；
可知 g[i] 就为以上两种情况下的最大值，即 g[i] = max(f[i - 1] + prices[i] - fee, g[i - 1])
3. 初始化与结果
初始状态：
- f[0] = -prices[0]
- g[0] = 0
最终结果为 g[n-1]。
4. 代码实现
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
if n == 0:
return 0
# f: 持有，g: 未持有
f = -prices[0]
g = 0
for i in (, n):
prev_f = f
f = (f, g - prices[i])
g = (g, prev_f + prices[i] - fee)
g
