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

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

 

思路：

试用动态规划，d[i][0]表示持有一只股票,d[i][1]表示没有持有股票，那么容易得到转移方程：

d[i][0] = max(d[i-1][0],d[i-1][1]-prices[i]);

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

 

代码：

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

        return d[n-1][1];
    }
};