Posted on 2023-10-17 21:57
Uriel 閱讀(61)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
DP 、
閑來(lái)無(wú)事重切Leet Code
給出找付費(fèi)工人刷每一面墻需要的paint時(shí)間time[i]和花費(fèi)cost[i]，如果付費(fèi)工人還在工作中，可以使用另一名免費(fèi)工人，免費(fèi)工人刷一面墻需要1時(shí)間，0花費(fèi)，問(wèn)刷完n面墻的最小花費(fèi)，背包問(wè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]