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

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

题解:

//贪心
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        //这题重点还是找最低点,更新最低点
        int ans = 0;
        int minprice=prices[0];
        for (int i = 0; i < prices.size(); i++)
        {
            //更新最小值,即为更新买入点
            if(prices[i]<minprice) minprice = prices[i]; 
            //涨得没有手续费多,不卖
            if(prices[i]>=minprice&&prices[i]-minprice<=fee)  continue; 
            //卖出并且更新最低点
            if(prices[i]-minprice> fee){
                ans+=prices[i]-minprice-fee; //更新利润
                //这里先把利润算进来,如果后面还能盈利,再-minprice的时候就抵消掉fee只算最开始的一次
                minprice=prices[i] -fee;   //全文精髓,这里更新minprice,继续持有股票
            }
        }
        return ans;
    }
};

//动态规划
class Solution {
public:
//dp[i][0]表示买入  更新 dp[i-1][0]||dp[i-1][1]-prices[i]
//dp[i][1]表示卖出  更新 dp[i-1][1] ||dp[i-1][0]+prices[i]-fee
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() <=1) return 0;
        vector<vector<int>> dp(prices.size(),vector(2,0));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for (int i = 1; i < prices.size(); i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i -1][1], dp[i -1][0]+prices[i]-fee);
        }
        return max(dp[prices.size()-1][1],dp[prices.size() -1][0]);
    }
};