Posted on 2023-10-17 21:57
Uriel 閱讀(45)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出找付費工人刷每一面墻需要的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]