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

    
        标签：
        
            股票问题
        
            LeetCode
        
    发布于：2022-02-04 20:47:13
    编辑于：2022-02-05 16:52:29
    浏览量：918

题目分析

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

Links: leetcode-714-best-time-to-buy-and-sell-stock-with-transaction-fee