Understanding the concise DP solution for best time to buy and sell stocks IV

user_3769451 0
Viewed 116

The problem is the famous leetcode problem (or in similar other contexts), best to buy and sell stocks, with at most k transactions. Here is the screenshot of the problem:

enter image description here

I am trying to make sense of this DP solution. You can ignore the first part of large k. I don't understand the dp part why it works.

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        # for large k greedy approach (ignore this part for large k)
        if k >= len(prices) / 2:
            profit = 0
            for i in range(1, len(prices)):
                profit += max(0, prices[i] - prices[i-1])
            return profit

#       Don't understand this part 
        dp = [[0]*2 for i in range(k+1)]
                             
        for i in reversed(range(len(prices))):
            for j in range (1, k+1):
                dp[j][True] = max(dp[j][True], -prices[i]+dp[j][False])
                dp[j][False] = max(dp[j][False], prices[i]+dp[j-1][True])
            
        return dp[k][True]

I was able to drive a similar solution, but that uses two rows (dp and dp2) instead of just one row (dp in the solution above). To me it looks like the solution is overwriting values on itself, which for this solution doesn't look right. However the answer works and passes leetcode.

dynamic-programming algorithm
1 Answers

Lets put words to it:

for i in reversed(range(len(prices))):

For each future price we already know in advance, after considering later prices.

  for j in range (1, k+1):

For each possibility of considering this price as one of k two-price transactions.

    dp[j][True] = max(dp[j][True], -prices[i]+dp[j][False])

If we consider this might be a purchase -- since we are going backwards in time, a purchase means a completed transaction -- we choose the best of (1) having considered the jth purchase already (dp[j][True]) or (2) subtract this price as a purchase and add the best result we have already that includes the jth sale (-prices[i] + dp[j][False]).

    dp[j][False] = max(dp[j][False], prices[i]+dp[j-1][True])

Otherwise, we might consider this as a sale (the first half of a transaction since we're going backwards), so we choose the best of (1) the jth sale already considered (dp[j][False]), or (2) we add this price as a sale and add to that the best result we have so far for the first (j - 1) completed transactions (prices[i] + dp[j-1][True]).

Note that the first dp[j][False] is referring to the jth "half-transaction," the sale if you will, since we are going backwards in time, that would have been set in an earlier iteration on a later price. We then can possibly overwrite it with our consideration of this price as a jth sale.

user_20347870
Related