#1105

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Filling Bookcase Shelves

Determine the minimum total height of a bookcase by placing books in order using state transition dynamic programming.

Problem Statement

You are given an array books where each books[i] = [thicknessi, heighti] represents the thickness and height of the ith book. A bookcase has shelves with a fixed width shelfWidth, and books must be placed in the order given. Each shelf can hold multiple consecutive books as long as their total thickness does not exceed shelfWidth.

When placing books on a shelf, the shelf's height is determined by the tallest book on that shelf. The goal is to stack all books while minimizing the sum of shelf heights. You must decide where to break shelves to ensure the overall bookcase height is as small as possible.

Examples

Example 1

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4

Output: 6

The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6. Notice that book number 2 does not have to be on the first shelf.

Example 2

Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6

Output: 4

Example details omitted.

Constraints

1 <= books.length <= 1000
1 <= thicknessi <= shelfWidth <= 1000
1 <= heighti <= 1000

Solution Approach

Dynamic Programming Definition

Define dp(i) as the minimum total height to place books[i:] on shelves. This directly applies the state transition dynamic programming pattern by building the solution from the end towards the start.

Iterate Over Shelf Options

For each starting index i, iterate through consecutive books adding them to the current shelf until shelfWidth is exceeded. Track the maximum height of books on this shelf and recursively compute dp(next_index) to find the total height for each configuration.

Compute Minimum Height

Select the option that yields the smallest total height and memoize dp(i) to avoid repeated calculations. This ensures the state transition is applied efficiently and adheres to the array and dynamic programming pattern of this problem.

Complexity Analysis

Metric	Value
Time	O(N \cdot W)
Space	O(N)

Time complexity is O(N \cdot W) because for each book we may examine up to W width for possible shelf placements. Space complexity is O(N) for storing dp values for each starting index.

What Interviewers Usually Probe

Check if you can place multiple consecutive books per shelf without exceeding shelfWidth.
Ask about defining the subproblem in terms of remaining books to apply state transition DP.
Consider memoization to optimize repeated calculations for overlapping subproblems.

Common Pitfalls or Variants

Common pitfalls

Not handling the shelf height correctly by always taking the maximum book height per shelf.
Failing to maintain the order of books, which is required for this problem's DP formulation.
Ignoring memoization, leading to excessive recursive calls and timeouts for larger inputs.

Follow-up variants

Allowing books to be rearranged arbitrarily changes the DP pattern and may require sorting strategies.
Using variable shelf widths for each level would require tracking multiple width states in DP.
Minimizing another metric, like total empty shelf space, shifts the state transition conditions.

FAQ

What is the key dynamic programming pattern for Filling Bookcase Shelves?

The main pattern is state transition DP, defining dp(i) as the minimum total height for books[i:] and iterating over shelf placement options.

Can books be placed out of order on shelves?

No, books must be placed in the given order, which is essential for the DP subproblem definition.

How do I track the shelf height when adding books?

Track the maximum height of books added to the current shelf; the shelf's height is determined by this maximum.

What happens if I exceed shelfWidth while placing books?

You must stop adding books to the current shelf and start a new shelf; exceeding shelfWidth is invalid.

Is memoization necessary for optimal performance?

Yes, memoization avoids recalculating dp(i) for the same starting index, ensuring O(N \cdot W) time efficiency.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ as the minimum height for placing the first $i$ books, initially $f[0] = 0$, and the answer is $f[n]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        f = [0] * (n + 1)
        for i, (w, h) in enumerate(books, 1):
            f[i] = f[i - 1] + h
            for j in range(i - 1, 0, -1):
                w += books[j - 1][0]
                if w > shelfWidth:
                    break
                h = max(h, books[j - 1][1])
                f[i] = min(f[i], f[j - 1] + h)
        return f[n]

Continue Practicing

#1125 smallest sufficient team #1130 minimum cost tree from leaf values #1139 largest 1 bordered square