# dp solution: mostly explanation

• I referred to this popular post. I noticed there was no much explanation in any post up till now, and so, decided to give a post, focusing on the explanation part. I'll post code after the whole explanation, you can also refer to this post to get JAVA/C++ version.

The dp array is two dimensional, and denoted as
dp[i][ind]
It's the maximum profit by at most i transactions till the end of ind day,
where i <= k and ind <= len(prices)-1. The final solution = dp[k][len(prices)-1]

Transition relation:
dp[i][ind], namely the maximum profit by making at most i transactions till the ind day =

1. no transaction done on ind day, the maximum profit is decided by the previous day, namely
dp[i][ind-1], the maximum profit by making at most i transactions till ind-1 day

2. the last selling transaction done on ind day, then the total maximum profit on ind day =
(profit from at most i-1 transactions till day x) + (profit by buying on x day and selling on ind day)
we need to go over all the x to find the maximum profit of this scenario. mathematically
max over x (dp[i-1][x] - prices[x]) + prices[ind] for 0 < x<= ind

in the end, dp[i][ind] = the larger one of the above two scenarios.

``````def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
"""
dp[i][ind] = max(dp[i][ind-1], dp[i-1][x] - prices[x] + prices[i])
= max(dp[i][ind-1], max(dp[i-1][x] - prices[x]) + prices[ind]) for x < ind

in code below, a variable m2 is used to record the maximum of choice 2, namely
max(dp[i-1][x] - prices[x]) + prices[i]) for x < ind
"""
def shortcut():
p = 0
i = 0
while i< L - 1:
p += max(prices[i+1] - prices[i], 0)
i += 1
return p

L = len(prices)
if k*2 >= L:
return shortcut()
dp = [0] * L
for i in xrange(1, k+1):
ndp = [None] * L
m2 = -prices[0]
ndp[0] = 0
for ind in xrange(1, L):
ndp[ind] = max(ndp[ind-1], m2 + prices[ind])
m2 = max(m2, dp[ind] - prices[ind])
dp = ndp
return dp[-1]
``````

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