Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
有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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理