2218. Maximum Value of K Coins From Piles

2218. Maximum Value of K Coins From Piles

這一個題目和 188. Best Time to Buy and Sell Stock IV 很類似，同時有兩件事情需要做決策。

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        
        @cache
        def dp(i, remaining):
            if i == len(piles):
                return 0
            if remaining == 0:
                return 0
            do_nothing = dp(i + 1, remaining)

            do_something = 0
            curr = 0
            for j in range(min(remaining, len(piles[i]))):
                curr += piles[i][j]
                do_something = max(do_something, curr + dp(i + 1, remaining - j - 1))
            
            return max(do_nothing, do_something)
        
        return dp(0, k)