• 欢迎光临~

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

开发技术 开发技术 2022-10-14 次浏览

问题描述

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];
    }
};
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com