aboutsummaryrefslogtreecommitdiff
path: root/painting_walls.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /painting_walls.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'painting_walls.py')
-rw-r--r--painting_walls.py31
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