leetcode

commit 5ef0b5615669fec24b4fac4ef6863f9d2b23e9f9
parent 06a16bbc1261b7587a5373b10c194649ab73d905
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 29 Dec 2023 16:47:04 +0000

Daily Problem

Diffstat:
A
Problems/1335.cpp
 | 
22
++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/1335.cpp b/Problems/1335.cpp
@@ -0,0 +1,22 @@
+class Solution {
+    static uint dp[11][301];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int minDifficulty(const vector<int> &jobDifficulty, int d, int idx = 0) const {
+        if (d == 0) return (idx != jobDifficulty.size()) * UINT_MAX;
+        if (jobDifficulty.size() - idx < d) return -1;
+        if (dp[d][idx] != UINT_MAX) return dp[d][idx];
+        uint res = UINT_MAX, maxi = 0;
+        for (int i = idx; i < jobDifficulty.size(); i++) {
+            maxi = max(maxi, (uint)jobDifficulty[i]);
+            const int next = minDifficulty(jobDifficulty, d - 1, i + 1);
+            if (next == UINT_MAX) continue;
+            res = min(res, maxi + next);
+        }
+        dp[d][idx] = res != UINT_MAX ? res : res - 1;
+        return res;
+    }
+};
+
+uint Solution::dp[11][301];
diff --git a/README.md b/README.md
@@ -660,6 +660,7 @@ for solving problems.
 |  1329  |   Medium   | [Sort the Matrix Diagonally](Problems/1329.cpp)                                                    |
 |  1333  |   Medium   | [Filter Restaurants by Vegan-Friendly, Price and Distance](Problems/1333.cpp)                      |
 |  1334  |   Medium   | [Find the City With the Smallest Number of Neighbors at a Threshold Distance](Problems/1334.cpp)   |
+|  1335  |    Hard    | [Minimum Difficulty of a Job Schedule](Problems/1335.cpp)                                          |
 |  1337  |    Easy    | [The K Weakest Rows in a Matrix](Problems/1337.cpp)                                                |
 |  1338  |   Medium   | [Reduce Array Size to The Half](Problems/1338.cpp)                                                 |
 |  1339  |   Medium   | [Maximum Product of Splitted Binary Tree](Problems/1339.cpp)                                       |