⚡Flashcard Drill➔
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

  1. Let dp[i] be the minimum total height for the first i books.
  2. The last shelf holds a contiguous suffix books[j..i-1], so try every start j and accumulate its thickness and maximum height.
  3. Stop extending the shelf once the accumulated thickness exceeds shelfWidth.
  4. Then dp[i] = min(dp[j] + max_height) over all valid j, with dp[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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems