2218. Maximum Value of K Coins from Piles - Explanation

1. Recursion

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)

        def dfs(i, coins):
            if i == n:
                return 0

            res = dfs(i + 1, coins)  # skip current pile
            curPile = 0
            for j in range(min(coins, len(piles[i]))):
                curPile += piles[i][j]
                res = max(res, curPile + dfs(i + 1, coins - (j + 1)))
            return res

        return dfs(0, k)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$ for the recursion stack.

Where $n$ is the number of piles and $k$ is the number of coins to choose.

2. Dynamic Programming (Top-Down)

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[-1] * (k + 1) for _ in range(n)]

        def dfs(i, coins):
            if i == n:
                return 0
            if dp[i][coins] != -1:
                return dp[i][coins]

            dp[i][coins] = dfs(i + 1, coins)  # skip current pile
            curPile = 0
            for j in range(min(coins, len(piles[i]))):
                curPile += piles[i][j]
                dp[i][coins] = max(dp[i][coins], curPile + dfs(i + 1, coins - (j + 1)))
            return dp[i][coins]

        return dfs(0, k)

Time & Space Complexity

Time complexity: $O(m * k)$
Space complexity: $O(n * k)$

Where $n$ is the number of piles, $k$ is the number of coins to choose, and $m$ is the total number of coins among all the piles.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for coins in range(k + 1):
                dp[i][coins] = dp[i + 1][coins]

                curPile = 0
                for j in range(min(coins, len(piles[i]))):
                    curPile += piles[i][j]
                    dp[i][coins] = max(
                        dp[i][coins],
                        curPile + dp[i + 1][coins - (j + 1)]
                    )

        return dp[0][k]

Time & Space Complexity

Time complexity: $O(m * k)$
Space complexity: $O(n * k)$

Where $n$ is the number of piles, $k$ is the number of coins to choose, and $m$ is the total number of coins among all the piles.

4. Dynamic Programming (Space Optimized)

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        dp = [0] * (k + 1)

        for pile in piles:
            for coins in range(k, 0, -1):
                curPile = 0
                for j in range(min(coins, len(pile))):
                    curPile += pile[j]
                    dp[coins] = max(dp[coins], dp[coins - (j + 1)] + curPile)

        return dp[k]

Time & Space Complexity

Time complexity: $O(m * k)$
Space complexity: $O(n * k)$

Where $n$ is the number of piles, $k$ is the number of coins to choose, and $m$ is the total number of coins among all the piles.