20.12.17 leetcode714

题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

题意：给你n天股票的价格，你可以在某天买入然后在某天卖出同时付出fee的手续费，最多只能保存一支股票，求最大利润。

分析：这道题相对于基础版多了手续费，不能直接贪心了，考虑用动态规划来做。

设dp0【i】为第i天时手头没股票，dp1[1]为第i天时手头有股票。

转移方程为dp0[i]=max(dp0[i-1],dp1[i-1]+prices[i]-fee)，dp1[i]=max(dp1[i],dp0[i-1]-prices[i]);

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