买卖股票的最佳时机含手续费
题目描述:

题目分析:
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


