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

Your are given an array of integers`prices`

, for which the`i`

-th element is the price of a given stock on day`i`

; and a non-negative integer`fee`

representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make.

#### Dynamic programming 1 – State machine

Similar to [Leetcode]122. Best Time to Buy and Sell Stock II, this is also a two-state problem, except that there’s a fee for each transaction. Therefore we can define `dp[i]`

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

and we have transition functions:

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

In this case we could have a O(n) time complexity and O(n) space complexity solution. Moreover, we can reduce the space complexity to O(1) since both `cash[i]`

and `hold[i]`

only depend on `cash[i-1]`

and `hold[i-1]`

.

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

#### Dynamic programming 2

Similar to [Leetcode]188. Best Time to Buy and Sell Stock IV, we can have another transition function as:

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

Therefore with a nested-loop, we have this O(n^2) solution:

```
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
dp = [max(0,prices[i]-prices[0]-fee) for i in range(len(prices))]
for i in range(1,len(prices)):
for j in range(1,i):
dp[i] = max(dp[i],dp[j-1]+prices[i]-prices[j]-fee)
dp[i] = max(dp[i],dp[i-1])
return dp[-1]
```

With a small tweak of the transition function, instead of looking for `max(prices[i]-prices[j]+dp[j-1]-fee)`

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

, reducing the time complexity to O(1).

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

#### Greedy

The general idea is to buy it at the lowest price and sell it at the highest. However, since there’s a fee for each transaction, it would affect our decisions. Take `prices=[1,4,3,9],fee=2`

as an example, if we buy `1`

and sell `3`

, then we wouldn’t achieve the largest profit as `(4-1)-fee+(9-3)-fee<(9-1)-fee`

.

One approach is that, after we buy `1`

and sell `4`

as `4-1-fee>0`

, we can assign `4-fee`

as our lowest price. When we find 9>(4-fee)+fee, then we can add `9-(4-fee)-fee`

to our profit. By using `price[i]-fee`

, we still hold the chance to explore the potential larger profit.

```
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
ret,buy = 0,float('inf')
for p in prices:
if p < buy:
buy = p
elif p>buy+fee:
ret += p-buy-fee
buy = p - fee
return ret
```