政子的博客

技术|学习|随笔

LeetCode-Best Time to Buy and Sell Stock IV

思路和 Best Time to Buy and Sell Stock III 类似，就是把只能买卖两次变成了可以买卖 k 次。但是需要注意的是这种情况下需要进行剪枝。因为在 k 太大的情况下，极容易出现内存超过限制，所以在k>=2/prices.size()的情况下应该及时认为这个情况下次数是不受限制的，然后按照次数不受限制的情况进行计算。

递推公式：

1
2
buy[j]=sell[j-1]-price[i]   if buy[j]<sell[j-1]+price[i]
sell[j]=buy[j]+price[i]     if sell[j]<buy[j]+price[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k==0) return 0;
        int size=(int)prices.size();
        if(k>=size/2) return doNormalMaxProfit(k,prices);
        else return doDpMaxProfit(k,prices);

    }
    int doNormalMaxProfit(int k, vector<int>& prices){
        int maxProfit=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i-1]<prices[i]){
                maxProfit+=prices[i]-prices[i-1];
            }
        }
        return maxProfit;
    }
    int doDpMaxProfit(int k, vector<int>& prices){
        int* buy=new int[k];
        int* sell=new int[k];
        for(int i=0;i<k;i++){
            buy[i]=INT_MIN;
            sell[i]=0;
        }
        for(int i=0;i<prices.size();i++){
            for(int j=0;j<k;j++){
                if(buy[j]<(j>0?sell[j-1]:0)-prices[i]) buy[j]=(j>0?sell[j-1]:0)-prices[i];
                if(sell[j]<buy[j]+prices[i]) sell[j]=buy[j]+prices[i];
            }
        }
        return sell[k-1];
    }
};