一、题目描述：
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意：
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
二、思路分析：
在之前买卖股票的最佳时机题中，增加了含有手续费，并且不限制购买次数。
此时，我们需要思考的是，当天的利润最大多少。
那么就会有两种情况：一种是今天持有，一种是今天不持有的情况。
最值情况可以使用动态规划：
我们可以定义两个dp数组，一个是不持有的dp1，一个是持有的dp2。两个数组初始值均为0。对于持有的，在刚开始需要持有股票，那么dp2[0] = -prices[0]。
找关系
dp1：从i= 1天开始遍历prices。在遍历prices时，对于不持有股票的dp1而言，当天的利润应该分两种情况：
- 昨天持有。今天卖掉。即：dp2[i-1] + prices[i] - fee。(dp2[i-1]为截至昨天的利润，可能为负，卖掉今天的价格属于收入，再减去手续费)
- 昨天不持有的。即：dp1[i-1]
此时dp1[i]应该取两者的最大值。
dp1[i]=Math.max(dp1[i−1],dp2[i−1]+prices[i]−fee)dp1[i] = Math.max(dp1[i-1], dp2[i-1] + prices[i] - fee)dp1[i]=Math.max(dp1[i−1],dp2[i−1]+prices[i]−fee)
dp2：对于持有股票的dp2而言，当天的利润应该分两种情况：
- 昨天持有。即：dp2[i - 1]
- 昨天不持有。 今天持有。即：dp2[i-1] - prices[i]。(dp2[i-1]为截至昨天的不持有最大利润，再买入今天股票的价格)
此时dp2[i]也应该取两者的最大值。
dp2[i]=Math.max(dp2[i−1],dp1[i−1]−prices[i])dp2[i] = Math.max(dp2[i - 1], dp1[i - 1] - prices[i])dp2[i]=Math.max(dp2[i−1],dp1[i−1]−prices[i])
最后返回当天不持有的最大利润即可。
例子1：
prices = [1,3,2,8,4,5], fee = 2
初始状态如下图：
开始循环：
最后，卖出最大利润为5。
三、AC 代码：
function maxProfit(prices: number[], fee: number): number { let dp1 = new Array(prices.length).fill(0) // 不持有 let dp2 = new Array(prices.length).fill(0) //持有 dp2[0] = -prices[0] for (let i = 1; i < prices.length; i++) { dp1[i] = Math.max(dp1[i - 1], prices[i] + dp2[i - 1] - fee) dp2[i] = Math.max(dp2[i - 1], dp1[i - 1] - prices[i]) } return dp1[prices.length - 1] };
四、总结：
遇到求最大值或最小值时，可以多考虑动态规划。求最值问题是属于动态规划的常见一类题型。
作者：ClyingDeng
链接：https://juejin.cn/post/6948708063621120030
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
