leetcode

commit 7e8b4b8f305eabbb95362c1b77d678f37dec7d90
parent 21ae357291d53efd4ef88bb4672af5dc2d2ceecf
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Nov 2023 13:08:49 +0000

1 Random Problem

Diffstat:
A
Problems/1105.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/1105.cpp b/Problems/1105.cpp
@@ -0,0 +1,19 @@
+class Solution {
+  public:
+    int minHeightShelves(const vector<vector<int>> &books, int shelfWidth) const {
+        static int dp[1001];
+        memset(dp, 0x7F, sizeof(dp));
+        const int n = books.size();
+
+        dp[0] = 0;
+        for (int i = 1; i <= n; i++) {
+            int left = shelfWidth, height = 0;
+            for (int j = i; j > 0 && books[j - 1][0] <= left; j--) {
+                left -= books[j - 1][0];
+                height = max(height, books[j - 1][1]);
+                dp[i] = min(dp[i], dp[j - 1] + height);
+            }
+        }
+        return dp[n];
+    }
+};
diff --git a/README.md b/README.md
@@ -528,6 +528,7 @@ for solving problems.
 |  1095  |    Hard    | [Find in Mountain Array](Problems/1095.cpp)                                                        |
 |  1099  |    Easy    | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)                          |
 |  1104  |   Medium   | [Path In Zigzag Labelled Binary Tree](Problems/1104.cpp)                                           |
+|  1105  |   Medium   | [Filling Bookcase Shelves](Problems/1105.cpp)                                                      |
 |  1109  |   Medium   | [Corporate Flight Bookings](Problems/1109.cpp)                                                     |
 |  1110  |   Medium   | [Delete Nodes And Return Forest](Problems/1110.cpp)                                                |
 |  1111  |   Medium   | [Maximum Nesting Depth of Two Valid Parentheses Strings](Problems/1111.cpp)                        |