Well explained Python DP with comments


  • 17
    J

    I think the general idea has been thoroughly explained by other brilliant leetcoders. All of the solutions are beautiful and concise. However, most of the them don't look obvious to me, so I wrote this and hope it looks more straight forward.
    It's O(kn), apparently not optimal. I name the key variables as local profit and global profit to make things much understandable (well, at least , to me). Performance is not too bad though.

    def maxProfit4(self, k, prices):
        n = len(prices)
        if n < 2:
            return 0
        # k is big enougth to cover all ramps.
        if k >= n / 2:
            return sum(i - j
                       for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
        globalMax = [[0] * n for _ in xrange(k + 1)]
        for i in xrange(1, k + 1):
            # The max profit with i transations and selling stock on day j.
            localMax = [0] * n
            for j in xrange(1, n):
                profit = prices[j] - prices[j - 1]
                localMax[j] = max(
                    # We have made max profit with (i - 1) transations in
                    # (j - 1) days.
                    # For the last transation, we buy stock on day (j - 1)
                    # and sell it on day j.
                    globalMax[i - 1][j - 1] + profit,
                    # We have made max profit with (i - 1) transations in
                    # (j - 1) days.
                    # For the last transation, we buy stock on day j and
                    # sell it on the same day, so we have 0 profit, apparently
                    # we do not have to add it.
                    globalMax[i - 1][j - 1],  # + 0,
                    # We have made profit in (j - 1) days.
                    # We want to cancel the day (j - 1) sale and sell it on
                    # day j.
                    localMax[j - 1] + profit)
                globalMax[i][j] = max(globalMax[i][j - 1], localMax[j])
        return globalMax[k][-1]

  • 0
    S

    you don't really need localMax[], use single variable instead. Since localMax[j] only depend on local localMax[j-1], the one before.


  • 1
    V

    Thank you for the excellent solution and explanation. Here is a more memory efficient version:

    def maxProfit(self, k, prices):
        if not prices:
            return 0
        
        n = len(prices)
        if k >= n // 2:
            return sum(
                x - y
                for x, y in zip(prices[1:], prices[:-1])
                if x > y)
        
        profits = [0] * n
        for j in range(k):
            # Update new_profits
            max_all = max_prev = max_here = 0
            for i in range(1, n):
                profit = prices[i] - prices[i-1]
                max_here = max(max_here + profit, max_prev + profit, max_prev)
                max_prev = profits[i]
                profits[i] = max_all = max(max_all, max_here)
        return profits[-1]
    

  • 0
    A

    Great and brilliant solution! I just make some modify to simplify the solution. Actually we only need to compare pre profit we made and profit we got in the for loop:

    class Solution(object):
        def maxProfit(self, k, prices):
            """
            :type k: int
            :type prices: List[int]
            :rtype: int
            """
        
            if not prices:
                return 0
            
            if k >= len(prices) // 2:
                return sum(
                    x - y
                    for x, y in zip(prices[1:], prices[:-1])
                    if x > y)
            
            
            profits = [0]*len(prices)
            for j in range(k):
    
                preprofit = 0
                for i in range(1,len(prices)):
                
                    profit = prices[i] - prices[i-1]
                    preprofit = max(preprofit+profit, profits[i])
                    profits[i] = max(profits[i-1], preprofit)
        
            return profits[-1]
    
    
    

Log in to reply
 

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