Filling Bookcase Shelves: Minimizing Height with DP

You have a sequence of books, each with a width and a height, and a bookcase where every shelf has the same maximum width. You must place the books in order on the shelves. The catch: each shelf's height equals the tallest book on it, and you want to minimize the total height of all shelves combined.

This is LeetCode 1105: Filling Bookcase Shelves, and it is a clean example of how DP helps you make optimal packing decisions when greedy approaches fall short.

Why greedy does not work

Your first instinct might be to greedily pack as many books as possible onto each shelf. After all, fewer shelves means less wasted vertical space, right? Not always. Imagine a short book followed by a tall one. If you pack them together, the shelf height jumps to match the tall book. But if you start a new shelf for the tall book, the previous shelf stays short and the total could be lower.

The order constraint (books must stay in sequence) means you cannot rearrange them. But you do get to choose where to place the "line breaks" between shelves. That choice at each position depends on all the books that follow, which is exactly the structure DP handles well.

Setting up the DP

Define dp[i] as the minimum total height needed to place the first i books. The answer will be dp[n] where n is the total number of books.

Base case: dp[0] = 0. Zero books need zero height.

Transition: For each book i, look backward and try adding books i, i-1, i-2, ... onto the same shelf. Keep a running width and track the maximum height among the books you are grouping. As long as the total width fits within shelfWidth, you have a valid shelf. For each valid grouping ending at some book j, the cost is dp[j-1] + max_height_of_books_j_through_i. Take the minimum across all valid groupings.

In other words, for each position you ask: "What if the current shelf starts at book j?" You try every valid starting point and pick the one that gives the smallest total.

The solution

def minHeightShelves(books, shelfWidth):
    n = len(books)
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        width = 0
        height = 0
        for j in range(i, 0, -1):
            width += books[j - 1][0]
            if width > shelfWidth:
                break
            height = max(height, books[j - 1][1])
            dp[i] = min(dp[i], dp[j - 1] + height)
    return dp[n]

The outer loop picks the book we are placing (1-indexed into dp). The inner loop walks backward, accumulating width and height for the current shelf. The moment the accumulated width exceeds shelfWidth, we stop. Otherwise, we check whether this grouping improves dp[i].

Step-by-step walkthrough

Let's trace through the example: books = [[1,3],[2,4],[3,2],[2,5],[1,2],[2,3]] and shelfWidth = 4.

Notice how the inner loop tries every valid shelf grouping. For dp[2], placing books 1 and 2 together (total width 3) gives height 4, which beats placing them on separate shelves (3 + 4 = 7). For dp[5], pairing books 4 and 5 lets book 5 "hide" under book 4's height for free, saving 2 units.

Why the inner loop goes backward

The inner loop counts backward from book i toward book 1. This is the natural direction because you are "extending" the current shelf by adding one more book to the left. At each step you accumulate width and update the running max height. Going backward means you can break as soon as the shelf overflows, which avoids unnecessary work.

Complexity analysis

The inner loop runs at most until the shelf overflows, which is bounded by shelfWidth / min_book_width. In the worst case (all books have width 1), the inner loop runs up to shelfWidth times per outer iteration. So the time complexity is O(n * shelfWidth) and the space is O(n) for the dp array.

The building blocks

This problem uses linear DP with a variable lookback window. It is the same fundamental structure as Coin Change, where dp[i] depends on several previous entries, but the lookback distance is bounded by a constraint (shelf width here, coin denominations there).

The key elements:

• State: dp[i] = minimum total height to shelve the first i books
• Transition: for each valid shelf grouping ending at book i, dp[i] = min(dp[j-1] + max_height) where j ranges over all valid starting points
• Base case: dp[0] = 0

You will see this same "scan backward, accumulate, and minimize" pattern in problems like:

• Minimum Cost to Cut a Stick (LeetCode 1547): partition a range optimally by trying every cut point
• Palindrome Partitioning II (LeetCode 132): partition a string into palindromes, minimizing cuts
• Split Array Largest Sum (LeetCode 410): partition an array to minimize the maximum subarray sum

Edge cases to watch for

• Single book: dp[1] = the book's height. Only one shelf needed.
• All books fit on one shelf: the total width is at most shelfWidth, so the answer is just the tallest book's height.
• Every book needs its own shelf: each book's width equals shelfWidth. The answer is the sum of all heights.
• Books with width 0: the constraints say width is at least 1, so you do not need to handle this.
• All books have the same height: any partition works and the answer is always n_shelves * height. The DP handles this naturally.

From understanding to recall

You can follow every step in this walkthrough. But can you reproduce the solution from scratch tomorrow? In a week? Under interview pressure?

The gap between understanding and recall is real. Spaced repetition bridges it. You revisit this shelf-packing DP at increasing intervals, write the recurrence from memory each time, and after a few reps the backward-scan pattern becomes automatic.

This variable-lookback DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Coin Change - The classic unbounded knapsack DP, same "look back by a bounded amount" structure
• Minimum Falling Path Sum - Another DP where each cell depends on a small window of previous values
• Partition Equal Subset Sum - A partition-based DP that decides how to split items optimally