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
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]
dp[i][ind], namely the maximum profit by making at most i transactions till the ind day =
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
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 =  * L for i in xrange(1, k+1): ndp = [None] * L m2 = -prices ndp = 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]