Description Link to heading

714.best-time-to-buy-and-sell-stock-with-transaction-fee

解题思路 Link to heading

We can consider this problem in two cases: owning stock and not owning stock, assuming that you need to pay transaction fee when selling stock.

  • owning stock:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i - 1]);
  • not owning stock:dp[i][1] = max(0, max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1] - fee));

Initializing dp:

  • dp[0][0] = -prices[0];
  • dp[0][1] = -fee;

Code Link to heading 

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