Leetcode 188: Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/.

Notes:

This is a classic dp problem. One of the important constrains is that we can only buy a stock first and then sell it later.

dp[k][i]: the most profits ending with the i-th element with at most k transactions.

At the i-th day, we have two choices:

1): no transaction;

2): we will perform a transaction. (we must sell the stock bought in a day j <= i)

Thus, dp[k][i] = max(dp[k][i-1], max(dp[k-1][j] + p[i] - p[j])); j<=i;

Let's make some reform of the above state-transition equation,

dp[k][i] = max(dp[k][i-1], max(dp[k-1][j] - p[j]) + p[i]);  j<=i;

define diffMax = max(diffMax, dp[k-1][j] - p[j]);

then dp[k][i] = max(dp[k][i-1], diffMax + p[i]);

Two things more:
1): if k >= len, then it become the question without no transaction time limit;
2): we can compress the two-D dp to a one-D one.


See the code below:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int len = prices.size();
        if(len < 2 || k < 1) return 0;

        if(k>=len) {
            int res = 0;
            for(int i=1; i<len; ++i) {
                int d = prices[i] - prices[i-1];
                if(d > 0) res += d;
            }
            return res;
        }

        vector<int> dp(len+1, 0);
        for(int i=0; i<k; ++i) {
            int diffMax = INT_MIN;
            for(int j=1; j<=len; ++j) {
                diffMax = max(diffMax, dp[j] - prices[j-1]);
                dp[j] = dp[j-1];
                dp[j] = max(dp[j], diffMax + prices[j-1]);
            }
        }
        return dp[len];
    }
};

Here I want to do a tentative brief summary of the Stock Problems on Leetcode.

Beside at most k transactions, there will be a fee for each transaction, as well as a cool-down time (colTime) when no transaction can be performed.

We just follow the above dp formula;

dp[k][i]: the most profits ending with the i-th element with at most k transactions.

At the i-th day, we have two choices:

1): no transaction;

2): we will perform a transaction. (we must sell the stock bought in a day j <= i)

Thus, dp[k][i] = max(dp[k][i-1], max(dp[k-1][j-colTime] + p[i] - p[j] - fee)); j<=i;

Let's make some reform of the above state-transition equation,

dp[k][i] = max(dp[k][i-1], max(dp[k-1][j-colTime] - p[j]) + p[i] - fee);  j<=i;

define diffMax = max(diffMax, dp[k-1][j-colTime] - p[j]);

then dp[k][i] = max(dp[k][i-1], diffMax + p[i] - fee).

See the code below:

class Solution {
public:
    int maxProfit(int k, int fee, int colTime, vector<int>& prices) {
        int len = prices.size();
        if(len < 2 || k < 1) return 0;

        vector<int> dp(len+1, 0);
        for(int i=0; i<k; ++i) {
            int diffMax = INT_MIN;
            for(int j=1; j<=len; ++j) {
                diffMax = max(diffMax, j >= colTime ? dp[j] - prices[j-1] : - prices[j-1]);
                dp[j] = dp[j-1];
                dp[j] = max(dp[j], diffMax + prices[j-1] - fee);
            }
        }
        return dp[len];
    }
};