有n堆硬币,每堆从上到下又有不同数量的几小堆coins,问最多取k堆,最多能取到多少coins,DP
思路参考->https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/solutions/3418159
1 #2218
2 #Runtime: 4968 ms (Beats 66.67%)
3 #Memory: 45.9 MB (Beats 33.33%)
4
5 class Solution(object):
6 def maxValueOfCoins(self, piles, k):
7 """
8 :type piles: List[List[int]]
9 :type k: int
10 :rtype: int
11 """
12 n = len(piles)
13 dp = [[0] * (k + 1) for _ in range(n + 1)]
14 for i in range(1, n + 1):
15 for coins in range(0, k + 1):
16 cnt = 0
17 for pr_coins in range(0, min(len(piles[i - 1]), coins) + 1):
18 if pr_coins:
19 cnt += piles[i - 1][pr_coins - 1]
20 dp[i][coins] = max(dp[i][coins], dp[i - 1][coins - pr_coins] + cnt)
21 return dp[n][k]