aboutsummaryrefslogtreecommitdiff
path: root/other/painting_walls.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/painting_walls.cpp')
-rw-r--r--other/painting_walls.cpp50
1 files changed, 0 insertions, 50 deletions
diff --git a/other/painting_walls.cpp b/other/painting_walls.cpp
deleted file mode 100644
index 5f70012..0000000
--- a/other/painting_walls.cpp
+++ /dev/null
@@ -1,50 +0,0 @@
-// 2742. Painting the Walls
-#include "leetcode.h"
-
-/*
- * 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 {
-public:
- int paintWalls(vector<int> &cost, vector<int> &time) {
- this->n = cost.size();
- vvd memo(n, vector<int>(n + 1));
- this->cost = cost;
- this->time = time;
- return dfs(0, n, memo);
- }
-
-private:
- int memo[501][501];
- vector<int> cost;
- vector<int> time;
- int n;
- int dfs(int curr, int left_wall, vvd & memo) {
- if (left_wall <= 0)
- return 0;
- if (curr == n)
- return 1e9;
- if (memo[curr][left_wall] != -1)
- return memo[curr][left_wall];
- int paid = cost[curr] + dfs(curr + 1, left_wall - 1 - time[curr], memo);
- int free = dfs(curr + 1, left_wall, memo);
- memo[curr][left_wall] = min(paid, free);
- return memo[curr][left_wall];
- }
-};
-
-int main() {
- Solution obj;
- vector<int> c1 = {1, 2, 3, 2}, c2 = {2, 3, 4, 2};
- vector<int> t1 = {1, 2, 3, 2}, t2 = {1, 1, 1, 1};
- printf("%d\n", obj.paintWalls(c1, t1)); // expect: 3
- printf("%d\n", obj.paintWalls(c2, t2)); // expect: 4
-}