leetcode

commit e122f6413731e67a59aeb2f0d858b1825fd21376
parent 7b16cedecc012943af1852b4903ba8777bc5de74
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 14 Oct 2023 17:48:15 +0000

Daily Problem

Diffstat:
A
Problems/2742.cpp
 | 
64
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 65 insertions(+), 0 deletions(-)
diff --git a/Problems/2742.cpp b/Problems/2742.cpp
@@ -0,0 +1,64 @@
+// Top-down
+class Solution {
+    static int dp[501][501];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int paintWalls(const vector<int> &cost, const vector<int> &time, int crnt = 0, int total = 0) {
+        if (total >= cost.size()) return 0;
+        if (crnt == cost.size()) return 1e9;
+        if (dp[crnt][total] != -1) return dp[crnt][total];
+
+        const int paint = cost[crnt] + paintWalls(cost, time, crnt + 1, total + time[crnt] + 1);
+        const int dont = paintWalls(cost, time, crnt + 1, total);
+        return dp[crnt][total] = min(paint, dont);
+    }
+};
+
+int Solution::dp[501][501];
+
+// Bottom-up
+class Solution {
+  public:
+    int paintWalls(const vector<int> &cost, const vector<int> &time) {
+        static unsigned dp[501][501];
+        memset(dp, 0x00, sizeof(dp));
+
+        const int n = cost.size();
+        for (int i = 1; i <= 500; i++)
+            dp[n][i] = 1e9;
+
+        for (int i = n - 1; i >= 0; i--) {
+            for (int remain = 1; remain <= n; remain++) {
+                const int paint = cost[i] + dp[i + 1][max(0, remain - time[i] - 1)];
+                const int dont = dp[i + 1][remain];
+                dp[i][remain] = min(paint, dont);
+            }
+        }
+
+        return dp[0][n];
+    }
+};
+
+// Space optimized Bottom-up
+class Solution {
+  public:
+    int paintWalls(const vector<int> &cost, const vector<int> &time) {
+        static unsigned dp[501], pdp[501];
+
+        const int n = cost.size();
+        for (int i = 1; i <= 500; i++)
+            pdp[i] = 1e9;
+
+        for (int i = n - 1; i >= 0; i--) {
+            for (int remain = 1; remain <= n; remain++) {
+                const int paint = cost[i] + pdp[max(0, remain - time[i] - 1)];
+                const int dont = pdp[remain];
+                dp[remain] = min(paint, dont);
+            }
+            swap(dp, pdp);
+        }
+
+        return pdp[n];
+    }
+};
diff --git a/README.md b/README.md
@@ -866,6 +866,7 @@ for solving problems.
 |  2707  |   Medium   | [Extra Characters in a String](Problems/2707.cpp)                                                  |
 |  2711  |   Medium   | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp)                          |
 |  2740  |   Medium   | [Find the Value of the Partition](Problems/2740.cpp)                                               |
+|  2742  |    Hard    | [Painting the Walls](Problems/2742.cpp)                                                            |
 |  2780  |   Medium   | [Minimum Index of a Valid Split](Problems/2780.cpp)                                                |
 |  2785  |   Medium   | [Sort Vowels in a String](Problems/2785.cpp)                                                       |
 |  2799  |   Medium   | [Count Complete Subarrays in an Array](Problems/2799.cpp)                                          |