Solution to the problem of stock algorithm framework

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];
}

 

210 original articles published, 42 praised, 80000 visitors+
Private letter follow

Tags: REST Python

Posted on Thu, 05 Mar 2020 20:39:27 -0800 by HERATHEIM