[LeetCode] 188. Best Time to Buy and Sell Stock IV

 Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

On each day, it has 2 states.

1. Buy stock. ( Buy stock on current day or bought stock on previous days )

2. Sell stock. ( Sell stock on current day or sold stock on previous days )

The answer is max profit can get if sell stock on last day.

Top-Down solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        buy, sell = 0, 1
        
        @lru_cache(maxsize = None)
        def dp(i, state, transaction):
            if state == buy and transaction == 0:
                # cannot buy when transaction == 0
                return -2 ** 31
            
            if state == sell and transaction == 0:
                # no profit when transaction == 0 
                return 0
            
            if i == 0 and state == buy:
                return -1 * prices[0]
            
            if i == 0 and state == sell:
                return 0
            
            if state == buy:
                # max( profit-of-buy-on-day-i [descrease transaction for selling on previous days], 
                #      profit-of-bought-on-previous-days )
                return max(-1 * prices[i] + dp(i-1, sell, transaction - 1), dp(i-1, buy, transaction))
            
            if state == sell:
                # max( profit-of-sell-on-day-i, profit-of-sold-on-previous-days )
                return max(prices[i] + dp(i-1, buy, transaction), dp(i-1, sell, transaction))
    
        if len(prices) <= 1:
            return 0
        
        # unlimited transaction when k is more than half of the amount of prices
        if k >= len(prices) // 2:
            profit = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        return dp(len(prices)-1, sell, k)

Bottom-Up solution:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        if n <= 1:
            return 0
        
        # unlimited transaction when k is more than half of prices
        if k >= n  // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profit += (prices[i] - prices[i-1])
                   
            return profit
        
        # dp[n][k+1][2]
        dp = [[[0, 0] for _ in range(k+1)] for _ in range(n)] 
        
        for i in range(n):
            dp[i][0][0] = 0  # sell on day i, transaction 0 
            dp[i][0][1] = -2 ** 31 # buy on day i, transaction 0 (impossible case)
        
        for j in range(1, k+1):
            dp[0][j][0] = 0
            dp[0][j][1] = -prices[0]
        
        for i in range(1, n):
            for j in range(1, k+1):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
        
        return dp[-1][-1][0]