Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

describe

There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2 piles: piles Explanation: The above diagram shows the different ways we can choose k coins. The maximum total we can obtain is 101.Copy the code

Example 2:

Input: piles = [[100], [100], [100], [100], [100], [100], [1,1,1,1,1,1,700]], k = 7 Output: 706 Explanation: The maximum total can be obtained if we choose all coins from the last pile.Copy the code

Note:

n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 10^5
1 <= k <= sum(piles[i].length) <= 2000
Copy the code

parsing

There are n stacks of coins on the table. Each stack consists of a positive number of coins of various denominations. We can only do it once, we can select coins from any pile of coins, take them out and add them to the wallet.

Given a list piles piles, where piles[I] is a list of integers representing the composition of piles I from top to bottom, and a positive integer K, return the maximum total value of coins k that can be held in a wallet.

We assume that DP[I][j] represents the maximum value of j coins in the first I cans, so the dynamic change relation of DP[I][j] is:

dp[i][j] = max(dp[i][j], dp[i-1][j-t]+preSum[i][t])
Copy the code

Where, if the i-th jar needs t coins, then dp[i-1][j-t] is the maximum value of j-T coins in the previous i-1 jar plus the total value of t coins in front of the current jar, which can be compared with dp[I][j] to take a larger value, and this is the current value of dp[I][j]. Of course, in the process of dynamic programming, we need to pay special attention to the boundary conditions, when I is 0, dp is 0. Finally, I just need to return DP [N][K-1], where N is piles length.

The time complexity of the piles was O(K * sum(I].length)), which means that despite the code having three layers in the piles, I had read through ALL the elements of the PILES once, basically on the order of 10^6, and just didn’t run out of time. The spatial complexity is O(sum(piles[I].length) * K).

answer

class Solution(object):
    def maxValueOfCoins(self, piles, k):
        """
        :type piles: List[List[int]]
        :type k: int
        :rtype: int
        """
        dp = [ [0]*2001 for _ in range(1001)]
        preSum = collections.defaultdict(list)
        N = len(piles)
        for i in range(N):
            total = 0
            preSum[i].append(total)
            for j in range(len(piles[i])):
                total += piles[i][j]
                preSum[i].append(total)

        for i in range(N):
            for j in range(k+1):
                for t in range(min(j, len(piles[i])) + 1):
                    current = (0 if i==0 else dp[i-1][j-t]) + preSum[i][t]
                    dp[i][j] = max(dp[i][j], current)
        return dp[N-1][k]		
Copy the code

The results

Runtime: Related content in Python online submissions for Maximum Value of K Coins. Memory Usage: Given in Python online submissions for Maximum Value of K Coins From Piles.Copy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation