LeetCode 188. Best Time to Buy and Sell Stock IV (动态规划)

class Solution {
public:
    int dp[10005];
    int bp[10005];
    int maxProfit(int k, vector<int>& prices) {
        
        if(k==0 || prices.size()<=1)
            return 0;
        
        for(int i=0;i<k&&i<prices.size()/2;i++)
        {
            int m = -99999999;
            for(int j=1;j<prices.size();j++)
            {
                m = max(m,bp[j-1]-prices[j-1]);
                
                dp[j] = max(dp[j-1],m+prices[j]);
            }
            
            for(int j=0;j<prices.size();j++)
            {
                bp[j]=dp[j];
                dp[j]=0;
            }
        }
        
        return bp[prices.size()-1];
        
    }
};