# Share Slightly Different Concise DP Approach, O(n*k), O(k) memory (beats 99%)

• ``````class Solution(object):
def maxProfit(self, k, prices):
if len(prices) < 2: return  0
if k < len(prices) / 2:
buy = [-1e18] * (k + 1)
sell = [0] * (k + 1)
for price in prices:
for i in range(1, k + 1):
sell[i] = max(sell[i], buy[i] + price)
return max(sell)
else:
prof = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
prof += prices[i] - prices[i - 1]
return prof
``````

I formulated this idea based on the solution for Buy and Sell Stock III where some solutions explained a state machine. We define the following dp functions:

``````buy[i][j] = Maximum profit at to buy stock at index i while making j'th buy tranxn
sell[i][j] = Maximum profit at to buy stock at index i while making j'th sell tranxn
``````

DP equations:

``````sell[i][j] = max(sell[i][j], buy[i - 1][j] + price[i])
``````

Since state for each j depends on only previous state (i - 1)
For each price:

``````sell[j] = max(sell[j], buy[j] + price)