Posted on 2023-10-14 17:27
Uriel 阅读(31)
评论(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]