题目描述

给定一个整数数组 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

代码实现

动态规划

其实这道题和买卖股票的最佳时机 IV的思路是一样的，只不过这里的手续费是固定的，所以可以直接在状态转移方程中减去手续费。

设置一个二维数组 dp 来表示每天的状态，dp[0] 表示不持有股票的最大利润，dp[1] 表示当天持有股票状态拥有的最大利润。然后根据题意进行状态转移：

  • 不持有股票：可以由原来不持有股票的状态转移过来，也可以由持有股票的状态转移过来（当天卖出），也就是 dp[0] = max(dp[0], dp[1]+prices[i])
  • 持有股票：可以由原来持有股票的状态转移过来，也可以由不持有股票的状态转移过来（当天买入），也就是 dp[1] = max(dp[1], dp[0]-prices[i]-fee)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func maxProfit(prices []int, fee int) int {
	dp := []int{0, -prices[0] - fee}

	for i := 1; i < len(prices); i++ {
        dp[0], dp[1] = max(dp[0], dp[1]+prices[i]), max(dp[1], dp[0]-prices[i]-fee)
	}

	return dp[0]
}

上面的代码最后返回的是 dp[0]，也就是不持有股票的最大利润。因为如果最后持有股票的话，一定会损失购买股票的价格，所以这里需要返回不持有股票的最大利润。

贪心算法

前面的算法中，在一开始购买的时候就减去了手续费，这样在计算利润的时候就不需要再减去手续费了。其实这里也可以使用贪心算法来解决这个问题。贪心算法的核心思想是每次都选择当前最优的解，而不是全局最优的解。书接上文买卖股票的最佳时机 II的贪心算法，遍历整个数组，判断当前价格和前一个价格的大小关系，如果当前价格大于前一个价格，就将差值累加到结果中。然后在每次交易的时候减去手续费：

1
2
3
4
5
6
7
8
9
10
11
func maxProfit(prices []int, fee int) int {
    maxProfit := 0

    for i := 1; i < len(prices); i++ {
        if profit := prices[i] - prices[i-1]; profit > 0 {
            maxProfit += profit - fee
        }
    }

    return maxProfit
}

把手续费放到一开始购买的时候减去，这样在计算利润的时候就不需要再减去手续费了。但是这里还需要思考一个问题，贪心算法是每次取局部最优解，最后到达全局最优解，但是由于有手续费的存在，局部最优解并不一定是全局最优解。比如 [1,3,7,5,10,3]，手续费为 3，如果在第 1 天以 1 的价格买入，在第 3 天以 7 的价格卖出，这样的利润是 7-1-3=3，然后在第 4 天以 5 的价格买入，在第 5 天以 10 的价格卖出，这样的利润是 10-5-3=2，最后的总利润是 3+2=5。而如果在第 1 天以 1 的价格买入，在第 5 天以 10 的价格卖出，这样的利润是 10-1-3=6。

这里如果按照之前的思路使用贪心算法，就是要判断每天交易后的收益是否更大于手续费，如果大于手续费就进行交易。所以其实股票问题直接用动态规划更通用。当然如果用贪心算法，这里就需要分类讨论一下各种情况，这里假设买入的价格为 buy：

  • 如果当前价格大于 buy，并且当前价格减去手续费小于 buy，就不进行交易，因为在当前价格买入和卖出都不够划算；
  • 如果当前价格小于 buy，那么不如在当前价格买入，而不是在之前的价格买入；
  • 如果当前价格大于 buy，并且当前价格减去手续费大于 buy，就进行交易。

而关键就在于第三种情况，因为此时进行了交易，但是后面的价格可能会继续上涨，并且这又会出现两种情况：

  • 当前交易不如当前持有而后面交易的收益大：[1,6,4,10]，如果在第 1 天以 1 的价格买入，在第 2 天以 6 的价格卖出，这样的利润是 6-1-3=2，然后在第 3 天以 4 的价格买入，在第 4 天以 10 的价格卖出，这样的利润是 10-4-3=3，最后的总利润是 2+3=5。而如果在第 1 天以 1 的价格买入，在第 4 天以 10 的价格卖出，这样的利润是 10-1-3=6。

  • 当前交易且后面再进行交易的收益更大：[1,6,1,10]，如果在第 1 天以 1 的价格买入，在第 2 天以 6 的价格卖出，这样的利润是 6-1-3=2，然后在第 3 天以 1 的价格买入，在第 4 天以 10 的价格卖出，这样的利润是 10-1-3=6，最后的总利润是 2+6=8。而如果在第 1 天以 1 的价格买入，在第 4 天以 10 的价格卖出，这样的利润是 10-1-3=6。

所以这里要对于第三种情况的交易增加一个后悔机制，也就是在交易后仍然可以以 0 手续费的形式继续在价格更高的时候卖出，因为手续费第一次卖出的时候已经减去了（也就是说 当卖出一支股票时，就立即获得了以相同价格并且免除手续费买入一支股票的权利）。

所以这里实现上就可以假设 buy 为最佳买入价格，默认为 prices[0]+fee，然后在遍历的时候判断当前价格减去手续费是否大于 buy，如果大于就进行交易（prices[i]-fee > buy），并且更新 buy 的值为当前价格减去手续费（buy = prices[i]-fee），否则判断按照当前价格买入是否更划算（prices[i]+fee < buy），如果更划算就更新 buy 的值。然后。这样就可以实现贪心算法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int, fee int) int {
	res := 0
	for i, buy := 1, prices[0]+fee; i < len(prices); i++ {
		if profit := prices[i] - buy; profit > 0 {
			res += profit
			buy = prices[i]
		} else if buyNow := prices[i] + fee; buyNow < buy {
			buy = buyNow
		}
	}

	return res
}

当然手续费也可以不在购入的时候减去，而是在卖出的时候减去：

1
2
3
4
5
6
7
8
9
10
11
12
13
func maxProfit(prices []int, fee int) int {
	res := 0
	for i, buy := 1, prices[0]; i < len(prices); i++ {
		if prices[i] < buy {
			buy = prices[i]
		} else if profit := prices[i] - buy - fee; profit > 0 {
			res += profit
			buy = prices[i] - fee
		}
	}

	return res
}

但是仍然要注意卖出的之后，更新 buy 的值为当前价格减去手续费（buy = prices[i]-fee），这样就等于后面的交易中免去手续费了。