2742.给墙壁刷油漆

链接：2742.给墙壁刷油漆
难度：Hard
标签：数组、动态规划
简介：请你返回刷完 n 堵墙最少开销为多少。

题解 1 - python

• 编辑时间：2024-06-29
• 执行用时：2024ms
• 内存消耗：492.34MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        @cache
        def dfs(idx: int, cur_time: int) -> int:
            if cur_time >= n - idx: return 0
            if idx == n: return inf
            return min(
                dfs(idx + 1, cur_time + time[idx]) + cost[idx],
                dfs(idx + 1, cur_time - 1)
            )
        return dfs(0, 0)