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.
Constraints:
n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000
思路:看数据范围应该是2维DP ,而2维DP就那么几种含义,套一下就能看出:
dp[i][j]表示:从1~i列,正好取出j个的最大值
class Solution(object):
def maxValueOfCoins(self, piles, k):
"""
:type piles: List[List[int]]
:type k: int
:rtype: int
"""
@functools.lru_cache(None)
def dp(p,q):
if p==-1: return 0
if q==0: return 0
cands = []
su = 0
for i in range(min(len(piles[p]),q)+1):
if i>=1: su+=piles[p][i-1]
cands.append(su+dp(p-1,q-i))
# print(p,q,cands)
return max(cands) if len(cands)>0 else 0
return dp(len(piles)-1,k)