The best time to buy and sell stocks Ⅳ (leetcode-188)

The best time to buy and sell stocks Ⅳ（LeetCode-188）

subject

Given an array of integers prices , It's the first i Elements prices[i] Is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most k transaction .

** Be careful ：** You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

Example 1：

 Input ：k = 2, prices = [2,4,1]
 Output ：2
 explain ： In the  1  God  ( Stock price  = 2)  Buy when , In the  2  God  ( Stock price  = 4)  Sell when , The exchange will make a profit  = 4-2 = 2 .

Example 2：

 Input ：k = 2, prices = [3,2,6,5,0,3]
 Output ：7
 explain ： In the  2  God  ( Stock price  = 2)  Buy when , In the  3  God  ( Stock price  = 6)  Sell when ,  The exchange will make a profit  = 6-2 = 4 .
      And then , In the  5  God  ( Stock price  = 0)  Buy when , In the  6  God  ( Stock price  = 3)  Sell when ,  The exchange will make a profit  = 3-0 = 3 .

Tips ：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

Ideas

At the best time to buy and sell stocks Ⅲ（LeetCode-123） after , I must understand, except for the State 0, The others are odd buy , Sell even

I won't write the five series , Direct reference to the best time to buy and sell stocks Ⅲ（LeetCode-123）

Code display

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