10-14 leetcode 2742

题意

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

A paid painter that paints the ith wall in time[i] units of time and takes cost[i] units of money.
A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.
Return the minimum amount of money required to paint the n walls.

题解

这题的题意有点扯，不过可以这样理解，如果一个付费工人在工作的时候，你可以同时用另外一位免费工人

那么这题可以转化为一个选或者不选的思路

选择付费工人刷第 i 块墙，那么刷前 i-time[i]-1 块墙的最小花费加上 cost[i] 就是刷前 i 块墙的最小花费
不选择付费工人刷第 i 块墙，那么刷前 i-1 块墙的最小花费就是刷前 i 块墙的最小花费

这题其实转化下来是一个 dp ，然后用滚动数组优化下空间就可以了

class Solution:
    def paintWalls(self, cost: list[int], time: list[int]) -> int:
        length = len(cost)
        dp = [float("inf")] * (length + 1)
        dp[0] = 0
        for i in range(length):
            for j in range(length, 0, -1):
                dp[j] = min(dp[j], dp[max(j - time[i] - 1, 0)] + cost[i])
        return int(dp[length])

这题实际上是个 01 背包问题的变种，不过背包容量是在不断变化的

Comments