dp solution: mostly explanation


  • 0
    N

    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]
    

Log in to reply
 

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