Python DP solution (state machine + explanation in detail)


  • -2
    L

    There are a total of 5 buy/sell stock questions, and there are two categories - limited most k transaction or unlimited transaction (with/without cool down day). Inspired by the following two answers, the state machine is the easiest way for me to understand (as a fresher in algorithm).

    1. unlimited transaction with cool down day

    https://leetcode.com/discuss/72030/share-my-dp-solution-by-state-machine-thinking

    1. limited most 2 transaction

    https://leetcode.com/discuss/48151/my-c-solution-o-n-time-o-1-space-8ms

    For this problem, we first need to consider if k > len(prices)/2. If yes, it is equivalent to unlimited transaction, and state machine idea 1) will be applied. Otherwise, state machine idle 2) will be applied.

    state machine idea 1)
    leave it for you to check the link

    state machine idea 2)

    State: For time i -

    s[i][0]: 1 buy;

    s[i][1]: 1 buy 1 sell; ...

    s[i][2*k-2]: k buy k-1 sell;

    s[i][2*k-1]: k buy k sell

    Initial value s[0]:

    a) If buy# == sell#, s[0][1::2] = 0

    b) 1 buy: s[0][0] = -prices[0]

    c) If buy# == sell#+1 i.e., s[0][2::2]: initialized to -2**31

    Step: For time i:

    a) If buy# == sell# (j%2 = 1) (sell stock from previous state), s[i][j] = max(s[i-1][j], s[i-1][j-1] + prices[i])

    b) 1 buy: s[0][0] = -prices[0]

    c) If buy# == sell#+1 (buy stock from previous sate), s[i][j] = max(s[i-1][j], s[i-1][j-1] - prices[i])

    class Solution(object):

    def maxProfit(self, k, prices):
        if not prices or not k:
            return 0
        
        l = len(prices)
        if k > l/2:
            s0 = [0] * l
            s1 = s0[:]
            s0[0], s1[0] = 0, -prices[0]
            for i in range(1, l):
                s0[i] = max(s0[i-1], s1[i-1] + prices[i])
                s1[i] = max(s1[i-1], s0[i-1] - prices[i])
            return s0[l-1]
            
        else:
            s = [[0] * 2 * k] * l
            s[0][1::2] = [0] * k
            s[0][0] = -prices[0]
            s[0][2::2] = [-2**31] * (k-1)
            for i in range(1, l):
                for j in range(2*k):
                    if j == 0:
                        s[i][0] = max(s[i-1][0], -prices[i])
                    elif j % 2 == 1:
                        s[i][j] = max(s[i-1][j], s[i-1][j-1] + prices[i])
                    else:
                        s[i][j] = max(s[i-1][j], s[i-1][j-1] - prices[i])
            return s[l-1][2*k-1]

Log in to reply
 

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