LeetCode Day 49 Dynamic Programming (10/17)

Having finished the hit-and-run problem, I’ve done LC122 before while practising the greedy algorithm, and now I’m going to do LC121 and 122 using dynamic programming.

Question 1

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

This problem can no doubt be solved by greedy methods, but since we’re practising dynamic programming, of course it’s time to apply the five parts of dynamic programming.

1. Determine the dp array (dp table) and the meaning of the subscripts
   1. dp[i][0] denotes the most cash from holding the stock on day i. Actually, the cash is 0 at the beginning, so adding the cash from buying the stock on day i is -prices[i], which is a negative number. dp[i][1] denotes the most cash from not holding the stock on day i.
2. Determining the Recursive Formula
   1. If the stock is held on day i, i.e., dp[i][0], then it can be derived from the two states
      1. If we hold the stock on day i-1, then we keep the status quo and the cash received is the cash received from holding the stock yesterday i.e.: dp[i - 1][0].
      2. Buy the stock on day i and the cash received is the cash received from buying today’s stock i.e.: -prices[i]
      3. Then dp[i][0] should be chosen to get the largest cash so dp[i][0] = max(dp[i - 1][0], -prices[i]);
      4. If the stock is not held on day i i.e. dp[i][1], it can also be introduced by two states
   2. If the stock is not held on day i-1, then the status quo is maintained and the cash received is the cash received from not holding the stock yesterday i.e., dp[i - 1][1].
      1. Sell the stock on day i and the cash received is the cash received from selling the stock at today’s price i.e.: prices[i] + dp[i - 1][0]
      2. Similarly dp[i][1] take the maximum, dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
3. How the dp array is initialised
   1. From the recursive formulas dp[i][0] = max(dp[i - 1][0], -prices[i]); and dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]); it can be seen that the basis for both is to be derived from dp[0][0] and dp[0][1].
   2. Then dp[0][0] indicates that the stock is held on day 0, and at this point the holding must be a stock purchase, because there can be no previous day to launch, so dp[0][0] -= prices[0]; dp[0][1] means no stock holdings on day 0, no stock holdings then cash is 0 so dp[0][1] = 0;
4. Determining the traversal order
   1. From the recursive formula you can see that dp[i] are derived from dp[i - 1], then it must be traversed from front to back.
5. Example of derivation of dp array

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])
        return dp[-1][1]

Question 2

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

The difference from the previous question is that the stock can now be bought and sold multiple times

So in this step of recursive formula, it will be different from the previous one.

So when you buy the stock, you may have the profit from the previous purchase and sale i.e.: dp[i - 1][1], so dp[i - 1][1] - prices[i].

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) 
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return dp[-1][1]