Leetcode Link: 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
题目
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
解法一
思路：相似问题是买卖股票的最佳时机II 本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以覆盖掉手续费的情况。
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
- 买入日期：其实很好想，遇到更低点就记录一下。
- 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
其他题解 1： 本题与之前的求解买卖股票差别很大 之前的买卖股票问题不需要计算手续费，利用贪心算法遍历一次，即可求得每种赚钱的可能性，将每此可以获得的利润相加得到答案。
考虑手续费，要考虑利润与手续费的关系，对于买入卖出的时间点的判断需要更加深刻。
每天对于股票的对待方式有三种
- 当今日价格比之前的最低点（当作之前买入的点）低的时候，可以取消之前的买入操作，换成今日买入。
- 当今日价格比之前买入点的价格高的时候，由于考虑手续费的问题，又要细分成两种。
- 首先考虑价格等于或高于之前价格（在没有手续费的情况下适宜卖出）但是减去手续费后不比之前价格高的情况。此种情况下需要继续持有，不做交易。 当价格减去手续费后，仍比之前买入时的价格(min_price)高时，卖出股票。但是要考虑到之后的价格如果更高，将会改在在后续的更高点卖出，此时就需要注意不能重复扣去手续费，所以要将min_price设置为price[i] - fee
其他题解2 问题可转化为 在购买时计入手续费 fee，且每天都可以进行股票买卖 的情况：
注意：在卖出股票时，可认为立即可以以相同价格且免除手续费购入股票。
当前购买价格（包含手续费）低于以往，选择此刻购入股票； 当前股票价格大于购买价格，选择此刻卖出股票获利，并同时免除手续费购入该股票。
题解：
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
ans = 0
buy = prices[0] + fee
for i in range(1, n):
if prices[i] + fee < buy:
buy = prices[i] + fee # 买入的最低价
elif prices[i] > buy:
ans += prices[i] - buy # 卖出获利【未必真的在此时卖出】
buy = prices[i] # 卖出的同时立即以原价买入
return ans解法二
从暴力递归到动态规划
暴力递归
只需要在买入的时候在减去一个手续费就可以。
class Solution: # 贪心思路
def maxProfit(self, prices: List[int], fee: int) -> int:
@functools.lru_cache()
def process(state, i):
if i == len(prices):
return 0
if state == 0:
p1 = process(0, i+1)
# 买入时注意考虑手续费
p2 = process(1, i+1) - prices[i] - fee
else:
p1 = process(1, i+1)
p2 = process(0, i+1) + prices[i]
return max(p1, p2)
return process(0,0)动态规划
class Solution: # 贪心思路
def maxProfit(self, prices: List[int], fee: int) -> int:
# [state, i]
dp = [[0 for _ in range(len(prices)+1)] for _ in range(2)]
for i in range(len(prices)-1, -1, -1):
dp[0][i] = max(dp[0][i+1], dp[1][i+1]-fee-prices[i]) # 注意考虑手续费
dp[1][i] = max(dp[1][i+1], dp[0][i+1]+prices[i])
return dp[0][0] 启发和联系
相关问题买卖股票的最佳时机II