LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee

Tag: 股票问题 LeetCode Posted on 2022-02-04 20:47:13 Edited on 2022-02-05 16:52:29 Views: 176

题目分析

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

这次每次交易后有费率,同样是无限交易次数。

动态规划法

懒得解释了,直接看同 tag 下其他问题的解释吧,这里唯一要注意的是,我们不能直接将 dp[0][1] 设置为 INT_MIN, 因为考虑到要减去 fee,可能导致溢出。

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/