Why is this problem tagged with "Dynamic programming"?


  • 10
    E

    Why is this problem tagged with "Dynamic programming"?


  • 0
    J

    I'm wondering too! I'm just leaving this here to get notification if somebody answer.


  • 43
    2

    I would like to answer this, to see whether my mind is clear.

    You can always see the solution similar to the format below.

    result = 0
    min_value = prices[0]
    for i in xrange(1, len(prices)):
        result = max(result, prices[i] - min_value)
        min_value = min(min_value, prices[i])
    return result
    

    But before that, take a look at the code below and see how it's derived.

    dp = [0] * len(prices)
    min_price = prices[0]
            
    for i in range(len(prices)):
        dp[i] = max(dp[i - 1], prices[i] - min_price)
        min_price = min(min_price, prices[i])
                
    return dp[-1]
    

    There's is a clear formula expression here, where dp[i] denotes the max profit on ith day.

    We should get the max profit on (i + 1)th day from

    • profit from previous days, or
    • profit gained on this day (current price - minimum price before)

    And only after this, we can update the minimum price.

    Then, according this 'naive' DP solution, we can see there's only one variable needed for memorization. So we change the array dp[] to a variable, and thus change the space from O(n) to O(1).

    (A good example of doing this reducing space would be knapsack problem. We can change the space complexity from O(mn) to O(n). I think you can discover that by yourself.)

    Let me know if this works for you.


  • 0
    E

    Thanks. I just figure it out by your answer!
    I use o(1) space just like your min_value, now I understand the dp[] idea.


  • 1
    Q
    day 0, 1, ..., n-1
    buy at day i, sell at day j, i<j
    max P[j] - P[i] with resepect to i, j, with constraint i<j
    = max { P[j] - P[i]  (i<j) }  w.r.t. j 
    = max { min P[i] w.r.t to i, (i<j)} w.r.t. j 
    where "=" meaning same (i,j) pair

  • 0
    F

    Here's an explanation why this is dynamic programming:

    We are looking for the most profitable trade. On any given day, I can either be in a trade, or not. If I'm in a trade, my profit at the end of that day is Profit(i) = prices[i] - prices[i-1] + Profit(i-1): the price movement today, plus the profit from yesterday. If I'm not in a trade, my profit is 0. Since I'm looking for profitable trades, I can take the max of that:

    Profit(i) = Math.max(prices[i] - prices[i-1] - Profit(i-1))
    

    We can write a loop to find profit on day i like this:

    let profit = []; profit[0] = 0;
    for(let i=1;i<prices.length;i++) {
       profit[i] = Math.max(prices[i] - prices[i-1] + profit[i-1], 0);
    }
    

    We don't actually need profit on all days, just max profit, so that's easy to simplify:

    let maxProfit = 0, prevProfit = 0;
    for(let i=1;i<prices.length;i++) {
       let profit = Math.max(prices[i] - prices[i-1] + prevProfit, 0);
       maxProfit = Math.max(profit, maxProfit);
       prevProfit = profit;
    }
    return maxProfit;
    

  • 1

    Because the problems later are relied on the problems before, such as we use MIN(i) to represent the lowest
    price before the ith day, and MAX(i) to represent the max profit before the ith day, so, for a string of length 6, when we consider the max profit of the whole process MAX(5), we found that it relied on all the days before it, so MIN(5) = min(prices[5], MIN(5)), MAX(5) = max(prices[5] - MIN(5), MAX(4)).


Log in to reply
 

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