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.

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

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        
        @cache
        def max_profit(i, k, stock_in_hand):
            if not i or k < 1:
                return 0 if not stock_in_hand else -prices[i]
            if stock_in_hand:
                return max(max_profit(i - 1, k, True), max_profit(i - 1, k - 1, False) - prices[i])
            else:
                return max(max_profit(i - 1, k, False), max_profit(i - 1, k, True) + prices[i])
                
        return max_profit(len(prices) - 1, k, False)