# Python DP solution (state machine + explanation in detail)

• 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).

1. unlimited transaction with cool down day

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

1. 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][1]: 1 buy 1 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]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.