Question type:

1) One transaction only, i.e. k = 1

2) Unlimited number of transactions, equivalent to k = +infinity (positive infinity)

3) 2 transactions, equivalent to k = 2

4) Unlimited number of times, but with the addition of transaction "freezing period" and "handling fee"

Frame building (using high-dimensional array to build state bit method):

dp[i][k][0 or 1]

i: Table days k: table remaining transactions [0 or 1]: table holding stock status

There are:

dp[i][k][0 or 1] is profit 0 <= i <= n-1, 1 <= k <= K n is the number of days, and K is the maximum number of transactions This problem has two states: n × K × 2, all of which can be solved by exhausting. for 0 <= i < n: for 1 <= k <= K: for s in {0, 1}: dp[i][k][s] = max(buy, sell, rest)

We can get the equation of state transition

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) Max (select rest, select sell) Explanation: today I don't own stocks. There are two possibilities: Either I didn't hold it yesterday, and today I choose rest, so I still don't hold it today; Either I held stocks yesterday, but today I sell, so I don't hold stocks today. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) Max (select rest, select buy) Explanation: today, I hold stocks. There are two possibilities: Or I held stocks yesterday, and today I choose rest, so I still hold stocks today; Or I didn't hold yesterday, but today I choose buy, so today I hold stocks.

Initialization value:

dp[-1][k][0] = 0 Explanation: since i starts from 0, i = -1 means that it hasn't started yet. At this time, of course, the profit is 0. dp[-1][k][1] = -infinity Explanation: it's impossible to hold stocks before the beginning. Use negative infinity to express the impossibility. dp[i][0][0] = 0 Explanation: since K starts from 1, k = 0 means that no transaction is allowed at all. At this time, the profit is certainly 0. dp[i][0][1] = -infinity Explanation: when trading is not allowed, it is impossible to hold stocks. Use negative infinity to express the impossibility.

2, Take the right medicine

Category 1: when K=1

Means that there is only one transaction, namely:

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) #When the stock is sold only, the number of remaining transactions will be reduced by 1 //Among them, the number of dp[i-1][0][0] Table energy transactions is 0, that is, dp[i-1][0][0]=0

Python (using temporary variable instead of transfer equation, time complexity O(1)):

dp_0,dp_1= 0, -float('inf') n=len(prices) for i in range(n): dp_0=max(dp_0 , dp_1 +prices[i]) #Not holding shares at the moment dp_1=max(dp_1 , -prices[i]) #Shares held at the moment return dp_0

Type 2: if the number of transactions is not limited, it is equivalent to k = +infinity (positive infinity)

At this time, the number of transactions is no longer a variable, but a constant, which has no effect on the transfer equation. It can be simplified and removed

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

Python (using temporary variable instead of transfer equation, time complexity O(1)):

dp_0,dp_1= 0, -float('inf') n=len(prices) for i in range(n): tmp=dp_0 dp_0=max(dp_0 , dp_1 +prices[i]) #No shares held at this time dp_1=max(dp_1 , tmp-prices[i]) #Shares held at the moment return dp_0

Type 3: 2 transactions, equivalent to k = 2

Then the equation of state transition is as follows:

dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]) dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]) dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1], -prices[i])

Python (using temporary variable instead of transfer equation, time complexity O(1)):

dp_1_0,dp_1_1= 0, -float('inf') dp_2_0,dp_2_1=0, -float('inf') n=len(prices) for i in range(n): dp_2_0=max(dp_2_0, dp_2_1+prices[i]) #No shares held at this time dp_2_1=max(dp_2_1, dp_1_0-prices[i]) #Shares held at the moment dp_1_0=max(dp_1_0, dp_1_1+prices[i]) dp_1_1=max(dp_1_1, -prices[i]) return dp_2_0

Type 4: conditions such as service charge

There is a commission to be paid for each transaction, as long as the Commission is subtracted from the profit.

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)

Type 5: wait one day after each sell to continue trading

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]) #Current holding stock = max (last holding stock, bought stock two times ago)

Python (using temporary variable instead of transfer equation, time complexity O(1)):

n=len(prices) dp_0,dp_1=0,-float('inf') #dp[i-1][0],dp[i-1][1] dp_pre=0 #dp[i-2][0] for i in range(n): tmp=dp_0 dp_0=max(dp_0,dp_1+ prices[i]) dp_1=max(dp_1,dp_pre-prices[i]) dp_pre=tmp return max(dp_0,0)

Type 7: the number of transactions k is variable

A transaction consists of buying and selling, which takes at least two days. Therefore, the effective limit K should not exceed n/2. If it is exceeded, there will be no constraint effect, which is equivalent to k = +infinity.

int maxProfit_k_any(int max_k, int[] prices) { int n = prices.length; if (max_k > n / 2) return maxProfit_k_inf(prices); int[][][] dp = new int[n][max_k + 1][2]; for (int i = 0; i < n; i++) for (int k = max_k; k >= 1; k--) { if (i - 1 == -1) { /* Handle base case */ } dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); } return dp[n - 1][max_k][0]; }