leetcode 2218. Maximum Value of K Coins From Piles （python）

描述

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
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

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.

Note:

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

解析

根据题意，桌子上有 n 堆硬币。 每堆由正数个各种面额的硬币组成。我们只能操作一次，可以选择任何一堆硬币上的硬币，将其取出并将其添加到钱包中。

给定一个列表 piles，其中 piles[i] 是一个整数列表，表示从上到下的第 i 堆硬币的组成，以及一个正整数 k，返回钱包中可以拥有的最大硬币总值 k 个硬币。

这道题很明显使用动态规划来做的，我们假定 DP[i][j] 表示在前 i 个罐子里取 j 个硬币的最大总值，那么 DP[i][j] 的动态变化关系就是 ：

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

其中假如第 i 个罐子要取 t 个硬币，那么 dp[i-1][j-t] 就是前 i-1 个罐子中取了 j-t 个硬币的最大总值加上当前罐子前 t 个硬币的总值，可以和 dp[i][j] 比较取较大值，这就是当前 dp[i][j] 的值。当然在动态规划过程中需要特别注意的就是注意边界条件，当 i 为 0 的时候 dp 值都为 0 。最后只需要返回 dp[N][k-1] 即可， N 是 piles 长度。

时间复杂度为 O(K * sum(piles[i].length) ) ，别看代码上是三层循环，其实就是遍历了一次 k ，还遍历了一次 piles 中所有的元素，基本在 10^6 数量级，刚刚没有超时，空间复杂度为 O(sum(piles[i].length) * K) 。

解答

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]		

运行结果

Runtime: 8252 ms, faster than 18.87% of Python online submissions for Maximum Value of K Coins From Piles.
Memory Usage: 53.6 MB, less than 30.19% of Python online submissions for Maximum Value of K Coins From Piles.

原题链接

leetcode.com/contest/wee…

您的支持是我最大的动力