This series of **Buy and Sell Stock I~VI** on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments.

- [Leetcode]121. Best Time to Buy and Sell Stock
- [Leetcode]122. Best Time to Buy and Sell Stock II
- [Leetcode]123. Best Time to Buy and Sell Stock III
- [Leetcode]188. Best Time to Buy and Sell Stock IV
- [Leetcode]309. Best Time to Buy and Sell Stock with Cooldown
- [Leetcode]714. Best Time to Buy and Sell Stock with Transaction Fee

Say you have an array for which thei^{th}element is the price of a given stock on dayi. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

#### Dynamic programming 1 – State Machine

Following the intuition using the state machine here in [Leetcode]121. Best Time to Buy and Sell Stock and [Leetcode]122. Best Time to Buy and Sell Stock II, let’s come up with the state transitions.

Here `hold`

means holding 1 stock, `cash`

means no stock in hands, and `rest`

means no stocks in hands and ready to buy one. Hence, it’s easy to give the transition functions:

```
hold[i] = max(hold[i-1],rest[i-1]-prices[i])
cash[i] = hold[i-1]+prices[i]
rest[i] = max(rest[i-1],cash[i-1])
```

`hold[i]`

means the largest profit we can make if we buy and hold the stock on day`i`

.`cash[i]`

means the largest profit we can make if we sell the stock on day`i`

.`rest[i]`

means the largest profit we can make if we rest on day`i`

.

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
rest,hold,cash = [0]*len(prices),[0]*len(prices),[0]*len(prices)
hold[0] = -prices[0]
for i in range(1,len(prices)):
hold[i] = max(rest[i-1]-prices[i],hold[i-1])
cash[i] = hold[i-1]+prices[i]
rest[i] = max(cash[i-1],rest[i-1])
return max(cash[-1],rest[-1])
```

Typically, we could also reduce the space complexity from O(n) to O(1).

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
rest,hold,sold = 0,float('-inf'),0
for price in prices:
prev_sold = sold
sold = hold+price
hold = max(rest-price,hold)
rest = max(prev_sold,rest)
return max(sold,rest)
```

#### Dynamic programming 2

Another way of using dynamic programming, as explained in [Leetcode]188. Best Time to Buy and Sell Stock IV, is that we can define `dp[i]`

as the largest profit we can make on day `i`

. Therefore the transition function is:

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

Note that the second item is using `dp[j-2]`

because:

- if we buy the stock on day
`j-1`

, then we can only use`dp[j-2]`

because we need to buy it on day`j`

. - if on day
`j-1`

we take the rest, then we can take`dp[j-1]`

. But since`dp[j-1]==dp[j-2]`

, the original transition function still holds.

Apparently we need a nested iteration to find the smallest `prices[i]-prices[j]+dp[i-2]`

. However, with a small tweak of the function, instead of looking for `max(prices[i]-prices[j]+dp[i-2])`

, we would look for `min(prices[j]-dp[j-2])`

. In this way we would be able to use a single variable to record this minimum value.

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
dp = [0] * (len(prices))
dp[0] = 0
dp[1] = max(0,prices[1]-prices[0])
low = min(prices[:2])
for i in range(2,len(prices)):
low = min(low,prices[i]-dp[i-2])
dp[i] = max(dp[i-1],prices[i]-low)
return dp[-1]
```