Problem Description

You are given a list of books, where each book is represented by a two-element list [thickness, height]. You are also given an integer shelfWidth representing the maximum width of each shelf. Your task is to place the books in order (they cannot be rearranged) onto shelves, such that:

• Each book must be placed on some shelf, in the given order.
• The sum of the thicknesses of books on a shelf must not exceed shelfWidth.
• The height of a shelf is the maximum height among all books on that shelf.
• The total height of the bookcase is the sum of the heights of all shelves used.

Your goal is to minimize the total height of the bookcase. There is always at least one valid arrangement. Do not skip or reuse books.

Thought Process

At first glance, this problem seems to invite a brute-force approach: try every possible way to break the sequence of books into shelves, and for each, compute the total height. However, this quickly becomes infeasible for large inputs because the number of ways to make such breaks grows exponentially.

To optimize, we recognize that the problem has optimal substructure: the best arrangement up to book i can be built from the best arrangement up to some previous book j, plus the cost of adding books j+1 to i on the last shelf. This is a classic setup for dynamic programming.

The main insight is to, for each book, consider all possible ways it could start a new shelf, and use previously computed optimal solutions for the subarrays before that point.

Solution Approach

• Dynamic Programming State: Let dp[i] represent the minimum total height needed to arrange the first i books.
• Initialization: dp[0] = 0 (no books means zero height).
• Transition:
  • For each i from 1 to n (number of books), try to place the last k books (for all possible k) on the same shelf, as long as their total thickness does not exceed shelfWidth.
  • For each possible k, compute the maximum height among these books (since the shelf height is determined by the tallest book), and update dp[i] as:
    dp[i] = min(dp[i], dp[j] + maxHeight)
    where j = i - k is the index before this shelf started.
• Final Answer: dp[n] gives the minimum total height for all books.

We use a simple array for dp because we only need to look back at previous values, and we scan leftward for each book to consider all valid shelf groupings.

Example Walkthrough

Let's use the following sample input:

• books = [[1,3],[2,4],[3,2]]
• shelfWidth = 6

1. First Book ([1,3]): Only one way to place it.
   dp[1] = 3
2. Second Book ([2,4]):
   • Place on new shelf: dp[2] = dp[1] + 4 = 7
   • Try to put with previous: thickness = 1+2=3 ≤ 6, max height = 4
     So, dp[2] = min(7, dp[0] + 4) = 4
3. Third Book ([3,2]):
   • New shelf: dp[3] = dp[2] + 2 = 6
   • Try with previous: thickness = 2+3=5 ≤ 6, max height = 4
     dp[3] = min(6, dp[1] + 4 = 7)
   • Try with all three: thickness = 1+2+3=6 ≤ 6, max height = 4
     dp[3] = min(6, dp[0] + 4 = 4)

Thus, the minimum total height is 4.

Code Implementation

class Solution:
    def minHeightShelves(self, books, shelfWidth):
        n = len(books)
        dp = [0] + [float('inf')] * n
        for i in range(1, n+1):
            width = 0
            height = 0
            # Try placing books[j:i] on the current shelf
            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]
      

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int width = 0, height = 0;
            for (int j = i; j > 0; --j) {
                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];
    }
};
      

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int width = 0, height = 0;
            for (int j = i; j > 0; --j) {
                width += books[j-1][0];
                if (width > shelfWidth) break;
                height = Math.max(height, books[j-1][1]);
                dp[i] = Math.min(dp[i], dp[j-1] + height);
            }
        }
        return dp[n];
    }
}
      

var minHeightShelves = function(books, shelfWidth) {
    const n = books.length;
    const dp = new Array(n+1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; ++i) {
        let width = 0, height = 0;
        for (let j = i; j > 0; --j) {
            width += books[j-1][0];
            if (width > shelfWidth) break;
            height = Math.max(height, books[j-1][1]);
            dp[i] = Math.min(dp[i], dp[j-1] + height);
        }
    }
    return dp[n];
};
      

Time and Space Complexity

• Brute-force: Would try all possible ways to split the array, leading to exponential time complexity: O(2ⁿ).
• Optimized DP Approach: For each book i, we may look back at all previous books (at most n), so the time complexity is O(n²).
• Space Complexity: The DP array uses O(n) space.

In practice, this is efficient enough for the problem's constraints.

Summary

By recognizing the optimal substructure of the problem, we avoid brute-force enumeration and instead use dynamic programming to efficiently compute the minimum total height for arranging books on shelves. The key insight is to, for each book, consider all ways to start a new shelf and use previously computed solutions. This leads to a clear, elegant, and efficient O(n²) solution.