We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Value of K Coins From Piles

Number: 1393

Difficulty: Hard

Paid? No

Companies: Microsoft, Google

Problem Description

Given n piles of coins where each pile is a list of coins (with the coin at index 0 representing the top), you are allowed to take coins from the top of any pile. In one move, you can remove the coin on top from any pile and add it to your wallet. The task is to choose exactly k coins from these piles, taking them optimally in order to maximize the total value in your wallet.

Key Insights

  • Use dynamic programming to solve the optimization problem.
  • Precompute prefix sums for each pile to quickly determine the total value when taking a certain number of coins from that pile.
  • Use a 1D dp array where dp[i] represents the maximum total value achievable with exactly i coins.
  • Iterate over each pile and update the dp array in reverse order to prevent using a coin more than once.
  • The problem is similar to a knapsack problem where you choose a number of coins from each pile without exceeding k total coins.

Space and Time Complexity

Time Complexity: O(n * k * t) where n is the number of piles, t is the maximum number of coins in a pile (with the overall sum of coins up to 2000), and k is the number of coins to pick. Space Complexity: O(k), using a 1D dp array of size k+1.

Solution

We use dynamic programming by maintaining an array dp where dp[j] stores the maximum value achievable using exactly j coins. For each pile, we first compute a prefix sum array to quickly look up the sum when taking the top x coins. We then iterate over the possible number of coins in reverse order (from k down to 0) and update dp[j] by checking whether taking x coins from the current pile combined with the best solution for j-x coins (stored in dp[j-x]) results in a higher total value. This ensures that the choices from each pile are optimally combined to get the overall maximum value when exactly k coins are chosen.

Code Solutions

def maxValueOfCoins(piles, k):
    # dp[j] will store the maximum total value for picking j coins
    dp = [0] * (k + 1)
    # Process each pile
    for pile in piles:
        # Compute prefix sums for the current pile
        prefix = [0]
        for coin in pile:
            prefix.append(prefix[-1] + coin)
        # Update dp array in reverse order
        for j in range(k, -1, -1):
            # Try taking x coins from current pile as long as it doesn't exceed j
            for x in range(1, min(len(pile), j) + 1):
                dp[j] = max(dp[j], dp[j-x] + prefix[x])
    return dp[k]

# Example usage:
piles = [[1, 100, 3], [7, 8, 9]]
k = 2
print(maxValueOfCoins(piles, k))  # Expected output: 101
← Back to All Questions