leetcode 714. Best Time to Buy and Sell Stock with Transaction Fee 动态规划DP

àì夳堔傛蜴生んèń 2022-06-03 08:53 97阅读 0赞

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:  
Input: prices = \[1, 3, 2, 8, 4, 9\], fee = 2  
Output: 8  
Explanation: The maximum profit can be achieved by:  
Buying at prices\[0\] = 1  
Selling at prices\[3\] = 8  
Buying at prices\[4\] = 4  
Selling at prices\[5\] = 9  
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.  
Note:

0 < prices.length <= 50000.  
0 < prices\[i\] < 50000.  
0 <= fee < 50000.

本题和建议和[leetcode 309. Best Time to Buy and Sell Stock with Cooldown 动态规划DP][leetcode 309. Best Time to Buy and Sell Stock with Cooldown _DP] 是一样的做法

建议和[leetcode 188. Best Time to Buy and Sell Stock IV 最大子段和][leetcode 188. Best Time to Buy and Sell Stock IV] 、[leetcode 123. Best Time to Buy and Sell Stock III 最大k次字段和 + DP][leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP] 、[leetcode 122. Best Time to Buy and Sell Stock II 最大子段和 + DP][leetcode 122. Best Time to Buy and Sell Stock II _ _ DP] 、[leetcode 121. Best Time to Buy and Sell Stock 最大字段和问题 + DP][leetcode 121. Best Time to Buy and Sell Stock _ _ DP] 一起学习。

注意本题和[leetcode 309. Best Time to Buy and Sell Stock with Cooldown 动态规划DP][leetcode 309. Best Time to Buy and Sell Stock with Cooldown _DP]才是一样的做法，**之前的k次交易DP设置的是第i次交易之后sell和buy的最大利益，但是对于本题和714是不限制交易次数，那么DP设置的是第一天buy和sell之后的最大利益，所以这个虽然都是DP，但是做法是不一样的。**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int maxProfit(vector<int>& prices, int fee) 
        {
            int n = prices.size();
            vector<int> buy(n, 0);
            vector<int> sold(n, 0);
            buy[0] = -prices[0];
            for (int i = 1; i < n; i++)
            {
                sold[i] = max(sold[i - 1], buy[i - 1] + prices[i] - fee);
                buy[i] = max(buy[i - 1], sold[i - 1] - prices[i]);
            }
            return sold[n - 1];
        }
    };

[leetcode 309. Best Time to Buy and Sell Stock with Cooldown _DP]: http://blog.csdn.net/jackzhang_123/article/details/78134159
[leetcode 188. Best Time to Buy and Sell Stock IV]: http://blog.csdn.net/jackzhang_123/article/details/78037522
[leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77988039
[leetcode 122. Best Time to Buy and Sell Stock II _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987707
[leetcode 121. Best Time to Buy and Sell Stock _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987643