714. Best Time to Buy and Sell Stock with Transaction Fee

题目描述

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

• 0 < prices.length <= 50000.
• 0 < prices[i] < 50000.
• 0 <= fee < 50000.

解题思路

显然，这是一道动态规划问题。对于这种问题而言，理解问题，并抽离出模型尤为关键。从题目可以知道，我们在每一天可以买、卖股票，或者什么都不做，但是约束是手里持有股票的股票数量最多为1（不能一次买多股，买之前必须先卖掉）。每次交易我们都需要付出一定的手续费。算出最后一天最大的利润值。

先从最后一条规则入手：买卖股票需要付手续费，也就是说，如果在当天同时买入又卖出股票，最后得到的利润是负数，显然是不符合题目要求的，因此，我们可以得出每天的操作只能是：买一次、卖一次、什么都不做。另外，如果我们要在某一天卖掉股票，由于当天买入立即卖出是不可行的，因此，在前一天，我们至少要持有股票。总结一下就是：

今天卖股票之后的利润=前一天手握这支股票时的利润+今天股票的价格-手续费

同理，如果今天我们需要买进股票：

今天买股票之后的利润=前一天没有股票时的利润-今天股票的价格

最后，如果今天什么都不做：

今天持有股票的利润=昨天持有股票的利润
今天没有股票的利润=昨天没有股票的利润

从上述的式子，我们不难总结出：每天的状态都分为是否持有股票两种情况。题目要求我们求出最后一天（N）能获得的最大利润，我们不妨可以这样考虑：

最后一天持有股票的利润=前一天持有股票的利润 | 前一天没有股票的利润-今天的价格
最后一天没有股票的利润=前一天没有股票的利润 | 前一天持有股票的利润+今天的价格-手续费

假设这时候我们已经知道了第N-1天没有持有股票时利润的最大值以及持有股票时利润的最大值，那么最后一天的持有股票和没有股票的利润的最大值就是：

最后一天持有股票的利润=MAX{前一天持有股票的利润, 前一天没有股票的利润-今天的价格}
最后一天没有股票的利润=MAX{前一天没有股票的利润, 前一天持有股票的利润+今天的价格-手续费}

第一天两种状态的利润是已知的，因此，无论N取什么值，都能算出当前N两种状态的最大值。由此总结出动态规划的状态转移方程：

// 0代表没有股票，1代表持有股票
profit[n][0] = max(profit[n-1][1] + price[n] - fee, profit[n-1][0])
profit[n][1] = max(profit[n-1][1], profit[n-1][0] - price[n])
return max(profit[n][0], profit[n][1])

一点优化

由于我们并不需要返回每天的最大利润，因此，记录下每天的状态和价格是没有必要的，只需要记录下前一天的两个状态，并且在今天的迭代中分别替换掉他们即可。

时间复杂度分析

每天的计算量为O(1)，遍历一次即可得到结果，复杂度为O(n)。

空间复杂度分析

如果不做优化，则需要开一个天数乘二大小的二维数组，复杂度为O(n)。优化后复杂度为O(1).

源码

class Solution {
public:
  int maxProfit(vector<int>& prices, int fee) {
    if (prices.size() == 0) {
      return 0;
    }
    int days = prices.size();
    int profits[50001][2] = {0};
    profits[0][1] = -prices[0];
    for (int i = 1; i < days; ++i) {
      profits[i][0] = max(profits[i-1][1] + prices[i] - fee, profits[i-1][0]);
      profits[i][1] = max(profits[i-1][1], profits[i-1][0] - prices[i]);
    }
    
    return profits[days-1][0] > profits[days-1][1] ? profits[days-1][0] : profits[days-1][1];
  }
};