There are a total of 5 buy/sell stock questions, and there are two categories - limited most k transaction or unlimited transaction (with/without cool down day). Inspired by the following two answers, the state machine is the easiest way for me to understand (as a fresher in algorithm).

- unlimited transaction with cool down day

https://leetcode.com/discuss/72030/share-my-dp-solution-by-state-machine-thinking

- limited most 2 transaction

https://leetcode.com/discuss/48151/my-c-solution-o-n-time-o-1-space-8ms

For this problem, we first need to consider if k > len(prices)/2. If yes, it is equivalent to unlimited transaction, and state machine idea 1) will be applied. Otherwise, state machine idle 2) will be applied.

**state machine idea 1)**

leave it for you to check the link

**state machine idea 2)**

** State:** For time i -

s[i][0]: 1 buy;

s[i][1]: 1 buy 1 sell; ...

s[i][2*k-2]: k buy k-1 sell;

s[i][2*k-1]: k buy k sell

*Initial value s[0]:*

a) If buy# == sell#, s[0][1::2] = 0

b) 1 buy: s[0][0] = -prices[0]

c) If buy# == sell#+1 i.e., s[0][2::2]: initialized to -2**31

** Step:** For time i:

a) If buy# == sell# (j%2 = 1) (sell stock from previous state), s[i][j] = max(s[i-1][j], s[i-1][j-1] + prices[i])

b) 1 buy: s[0][0] = -prices[0]

c) If buy# == sell#+1 (buy stock from previous sate), s[i][j] = max(s[i-1][j], s[i-1][j-1] - prices[i])

class Solution(object):

```
def maxProfit(self, k, prices):
if not prices or not k:
return 0
l = len(prices)
if k > l/2:
s0 = [0] * l
s1 = s0[:]
s0[0], s1[0] = 0, -prices[0]
for i in range(1, l):
s0[i] = max(s0[i-1], s1[i-1] + prices[i])
s1[i] = max(s1[i-1], s0[i-1] - prices[i])
return s0[l-1]
else:
s = [[0] * 2 * k] * l
s[0][1::2] = [0] * k
s[0][0] = -prices[0]
s[0][2::2] = [-2**31] * (k-1)
for i in range(1, l):
for j in range(2*k):
if j == 0:
s[i][0] = max(s[i-1][0], -prices[i])
elif j % 2 == 1:
s[i][j] = max(s[i-1][j], s[i-1][j-1] + prices[i])
else:
s[i][j] = max(s[i-1][j], s[i-1][j-1] - prices[i])
return s[l-1][2*k-1]
```