HardNo. 2742
Painting the Walls — LeetCode 2742 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if n - i <= j:
return 0
if i >= n:
return inf
return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1))
n = len(cost)
return dfs(0, 0)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2742. Painting the Walls is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2741 | Special Permutations | Medium |
| 2746 | Decremental String Concatenation | Medium |
| 2750 | Ways to Split Array Into Good Subarrays | Medium |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
Frequently asked questions
- How hard is LeetCode 2742. Painting the Walls?
LeetCode 2742. Painting the Walls is rated Hard on LeetCode.
- What topics does LeetCode 2742. Painting the Walls cover?
LeetCode 2742. Painting the Walls is tagged Array and Dynamic Programming on LeetCode.