Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出找付费工人刷每一面墙需要的paint时间time[i]和花费cost[i],如果付费工人还在工作中,可以使用另一名免费工人,免费工人刷一面墙需要1时间,0花费,问刷完n面墙的最小花费,背包问题

 1 #2742
 2 #Runtime: 858 ms (Beats 33.33%)
 3 #Memory: 13.3 MB (Beats 33.33%)
 4 
 5 class Solution(object):
 6     def paintWalls(self, cost, time):
 7         """
 8         :type cost: List[int]
 9         :type time: List[int]
10         :rtype: int
11         """
12         n = len(cost)
13         dp = [0] + [float('inf')] * n
14         for i in xrange(n):
15             for j in range(n, 0, -1):
16                 dp[j] = min(dp[j], dp[max(0, j - time[i] - 1)] + cost[i])
17         return dp[n]

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