LeetCode Day 50 Dynamic Programming (11/17)

Continuing with the stock trading exercise, but today it is more difficult and the LeetCode is labelled as Hard.

Question 1

123. Best Time to Buy and Sell Stock III

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

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Although the number of times it takes to sell a stock has gone from one to two, it’s a lot harder than it was before. There is more variety in the options of choosing not to sell one day, or choosing to sell one or both.

When choosing the recursive formula to reach the dp[i][1] state, there are two specific operations:

• Operation 1: the stock was bought on day i, then dp[i][1] = dp[i-1][0] - prices[i]
• Operation 2: No operation is done on day i. Instead, it follows the state of buying on the previous day, i.e.: dp[i][1] = dp[i - 1][1]

So does dp[i][1] pick dp[i-1][0] - prices[i], or dp[i - 1][1]?

It must be the biggest one, so dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

Similarly dp[i][2] has two operations:

• Operation 1: the stock is sold on day i, then dp[i][2] = dp[i - 1][1] + prices[i]
• Operation 2: There is no operation on day i, and it follows the state of the stock sold on the previous day, i.e.: dp[i][2] = dp[i - 1][2]

So dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

The same reasoning can be introduced for the remaining state part:

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

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

Question 2

188. Best Time to Buy and Sell Stock IV

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

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Compared to the previous question, the number of transactions is limited. In a two-dimensional recursive array, it can be found that

Except for 0, an even number is a sell and an odd number is a buy.

The requirement of the question is that there should be at most k transactions, so the range of j is just defined as 2 * k + 1.

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