diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /painting_walls.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'painting_walls.py')
-rw-r--r-- | painting_walls.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/painting_walls.py b/painting_walls.py new file mode 100644 index 0000000..5661285 --- /dev/null +++ b/painting_walls.py @@ -0,0 +1,31 @@ +# 2742. Painting the Walls + +""" +you are given two 0-indexed integer arrays, cost and time of size n +representing the costs and the time taken to paint n walls respectively. +there are two painters available: +- a paid painter that paints the i'th 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. +""" + + +class Solution(object): + def paintWalls(self, cost, time): + n = len(cost) + dp = [[0x3F3F3F3F3F3F for i in range(n + 1)] for j in range(n + 1)] + dp[0][0] = 0 + for i in range(n): + for j in range(n + 1): + t = min(n, j + time[i] + 1) + dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]) + dp[i + 1][t] = min(dp[i + 1][t], dp[i][j] + cost[i]) + return dp[n][n] + + +if __name__ == "__main__": + obj = Solution() + print(obj.paintWalls([1, 2, 3, 2], [1, 2, 3, 2])) # expect: 3 + print(obj.paintWalls([2, 3, 4, 2], [1, 1, 1, 1])) # expect: 4 |