# 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}:
```

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])

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+

Tags: REST Python

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