买卖股票的最佳时机含手续费

题目表述

给定一个整数数组 prices，其中 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

示例 2

输入：prices = [1,3,7,5,10,3], fee = 3

输出：6

提示

1 <= prices.length <= 5 * 104

1 <= prices[i] < 5 * 104

0 <= fee < 5 * 104

解法一：动态规划

记买入为负利润，卖出为正利润；设dp0[i],dp1[i]分别表示第i天不持有股票和持有股票，则可得状态转移方程：

$$dp0[i]=max(dp0[i-1],dp1[i-1]+prices[i]-fee)$$$$dp1[i]=max(dp1[i-1],dp0[i-1]-prices[i])$$

时间复杂度：O(n)，空间复杂度：O(1)

代码实现

from typing import List


class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # 持有：dp0[i] = max(dp0[i-1], dp1[i-1]-prices[i])
        # 未持有：dp1[i] = max(dp1[i-1], dp0[i-1]+prices[i]-fee)
        dp0, dp1 = -prices[0], 0
        for v in prices[1:]:
            dp0, dp1 = max(dp0, dp1-v), max(dp1, dp0+v-fee)
        return dp1

package leetcode

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func maxProfit(prices []int, fee int) int {
	// 持有：dp0[i] = max(dp0[i-1], dp1[i-1]-prices[i])
	// 未持有：dp1[i] = max(dp1[i-1], dp0[i-1]+prices[i]-fee)
	dp0, dp1 := -prices[0], 0
	for _, v := range prices[1:] {
		dp0, dp1 = max(dp0, dp1-v), max(dp1, dp0+v-fee)
	}
	return dp1
}