714.best-time-to-buy-and-sell-stock-with-transaction-fee 买卖股票的最佳时机含手续费

问题描述

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

解题思路

分为手中有股票和无股票两种情况讨论，设定在卖出股票时支出手续费:

• 手中有股票: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));

初始化:

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

代码

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];
    }
};