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

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

给定一个整数数组 prices ，其中 prices[i] 表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续

示例：

输入：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

动态规划

依旧是对交易的次数不进行限制，但是每买卖一次都会产生相应的手续费。使用动态规划求解，重点依旧是动态规划数组的定义。本题相对于122.买卖股票的最佳时机II改变的仅仅是卖出环节需要收取手续费，那么就需要修改递推公式。

1. 动态规划数组的定义：定义动态规划数组 dp[n][2] ，其中 dp[i][0] 表示在第 i 天持有股票所拥有的最大现金数， dp[i][1] 表示在第 i 天不持有股票所拥有的最大现金数

2. 动态规划数组的推导：分别推导 dp[i][0] 和 dp[i][1]

对于 dp[i][0] 的推导：

• 前一天持有： dp[i][0]=dp[i-1][0]
• 前一天不持有： dp[i][0]=dp[i-1][1]-prices[i]

对于 dp[i][1] 的推导：

• 前一天持有： dp[i][1]=dp[i-1][0]+prices[i]-fee
• 前一天不持有： dp[i][1]=dp[i-1][1]

总体的推导为：

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
dp[i][1]=max(dp[i-1][0]+prices[i]-fee,dp[i-1][1]);

1. 动态规划数组的初始化：在第一天 dp[0][0]=-peices[0] 买入，不持有只需不买入 dp[0][1]=0

2. 动态规划数组的遍历顺序：从前向后遍历

3. 举例验证：对于 prices = [1, 3, 2, 8, 4, 9], fee = 2 动态规划数组的变化过程为：（仅展示最后一位）

dp[i]
-1 0
-1 0
-1 0
-1 5
1 5
1 8

代码实现：基于滚动数组实现

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

贪心实现

此处要基于贪心实现，相较于122.买卖股票的最佳时机II是有区别的，在122题中，不限交易次数的同时，交易是不需要手续费的，因此可以单纯的寻找全部的单调区间相加即可。

此处要基于贪心实现：将手续费的计算转移到股票买入阶段，使用一个变量 buy 记录买入股票的费用，假设在第 i 天买入，那么 buy=prices[i]+fee ，从前向后遍历 prices 数组。

• 当 prices[i]+fee<buy 时，说明在当天买入股票，能够使用更少的花费，那么对 buy 进行更新。
• 当 prices[i]>buy 时，也就是在当天卖出是能够盈利的，但是并不能保证全局最优，但是在全局最优的情形下，这一部分的利润是一定能够赚取的，因此将这一部分利润加入总利润，并且令 buy=prices[i] ，不加手续费的原因在于当天并不是真的卖出后买入，主要是为了更新花费，在此基础上，若是后一天 prices[i+1]>buy 也就是说明在后面买可以赚更多，继续抽取利润，更新费用 buy=prices[i+1] ，若是 prices[i+1]+fee<buy 也就是在后一天已经不能赚钱，此时就在后一天假设买入 buy=prices[i+1]+fee (也就是在前一天实际进行了卖出)

代码实现：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        int profit=0;
        int buy=prices[0]+fee;
        for(int i=1;i<n;i++){
            if(prices[i]+fee<buy){
                buy=prices[i]+fee;
            }else if(prices[i]>buy){
                profit+=prices[i]-buy;
                buy=prices[i];
            }
        }
        return profit;
    }
};