leetcode 188. Best Time to Buy and Sell Stock IV

Problem Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution

股票买入卖出，最多交易k次的最大利润。动态规划，而不能简单的用一个dp[i][j]表示在第i天，j次交易内达到的最大利润。因为状态转移无法只靠这一个状态完成。

两个状态：dp1[i][j]表示在第i天，j次交易且第i天卖出，能获得的最大利润。dp2[i][j]表示在第i天之前，j次交易能获得的最大利润。状态转移：dp1[i][j] = max(dp2[i-1][j-1] + max(0,diff), dp1[i-1][j] + diff); dp2[i][j] = max(dp1[i-1][j], dp2[i-1][j])。此外还要注意如果k比较大，就退化成了没有k约束的问题了，这种情况下O(n)解决。

Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // dp1[i][j] = max(dp2[i-1][j-1] + diff, dp1[i-1][j] + diff)
        // dp2[i][j] = max(dp2[i-1][j], dp1[i][j])
        if(k >= prices.size()) {
            int ret = 0; 
            for(int i = 1; i < prices.size(); i++) {
                if(prices[i] > prices[i-1]) ret += prices[i] - prices[i-1];
            }
            return ret;
        }
        vector<int> dp1 = vector<int>(k+1, 0);
        vector<int> dp2 = vector<int>(k+1, 0);
        for(int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i-1];
            for(int j = k; j >= 1; j--) {
                dp1[j] = max(dp2[j-1] + max(0, diff), dp1[j] + diff);
                dp2[j] = max(dp2[j], dp1[j]);
                // printf(" (%d %d) ", dp1[j], dp2[j]);
            }
            // cout<<endl;
        }
        return dp2[k];
    }
};