NeetCode #676LC-1105Medium1-D Dynamic Programming
← Back to All Problems#676 · #1105 · Filling Bookcase Shelves(填充书架)
📌 Problem Statement & Constraints
Books must be placed in order on shelves of width
shelfWidth. Each book has a thickness and a height; the height of a shelf is the maximum book height on it, and the total height is the sum over shelves. Return the minimum possible total height. Constraints: 1 <= books.length <= 1000, 1 <= thickness_i, height_i <= shelfWidth.💡 Core Algorithmic Approaches
- Let
dp[i]be the minimum total height for the firstibooks. - The last shelf holds a contiguous suffix
books[j..i-1], so try every startjand accumulate its thickness and maximum height. - Stop extending the shelf once the accumulated thickness exceeds
shelfWidth. - Then
dp[i] = min(dp[j] + max_height)over all validj, withdp[0] = 0.
💻 Benchmark Python3 Implementation
class Solution:
def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
dp = [0] + [float("inf")] * n
for i in range(1, n + 1):
width = 0
height = 0
j = i
while j > 0: # shelves ending at book i-1
width += books[j - 1][0]
if width > shelfWidth:
break # this book no longer fits
height = max(height, books[j - 1][1])
dp[i] = min(dp[i], dp[j - 1] + height)
j -= 1
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2) worst case; each shelf holds a limited number of books so it is usually faster.
💾 Space Complexity
O(n): the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Filling shelves greedily: a tall book is sometimes better moved to its own shelf, so greedy is not optimal.
- Sorting the books: the order is fixed by the problem statement.
- Forgetting
dp[0] = 0: the empty prefix has height 0 and anchors the recurrence. - Continuing past the width limit: once a book does not fit, the shelf must end, so the loop must break.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.