Painting the Walls Python Solution with Tests

lcpy gen -n 2742   # by problem number
lcpy gen -s painting_the_walls   # by problem name

Input: cost = [1,2,3,2], time = [1,2,3,2]
Output: 3
Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

Input: cost = [2,3,4,2], time = [1,1,1,1]
Output: 4
Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

class Solution:
    # Time: O(n^2)
    # Space: O(n)
    def paint_walls(self, cost: list[int], time: list[int]) -> int:
        n = len(cost)
        # dp[j] = min cost of paid walls so the free painter can cover j walls;
        # a paid wall with time t covers itself plus t free walls.
        inf = 10**18
        dp = [0] + [inf] * n
        for c, t in zip(cost, time, strict=True):
            for j in range(n, 0, -1):
                candidate = dp[max(0, j - t - 1)] + c
                if candidate < dp[j]:
                    dp[j] = candidate
        return dp[n]