Filling Bookcase Shelves

medium dynamic programming array

Problem

You are given books in order, where books[i] = [thickness, height], and a shelf width shelfWidth. Place the books in the given order onto shelves: each shelf may hold a contiguous group of books whose total thickness is at most shelfWidth, and the height of a shelf equals the tallest book on it. Return the minimum possible total height of the bookcase.

Inputbooks = [[1,3],[2,4],[3,2]], shelfWidth = 6

Output4

All three books fit on one shelf (thickness 1 + 2 + 3 = 6 = shelfWidth), so the total height is just the tallest book, 4. Any split would add heights of separate shelves and cost more.

books (e.g. 1x1, 2x3, 2x3, 1x1, 1x1)

shelfWidth

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

function minHeightShelves(books, shelfWidth) {
  const n = books.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let width = 0, height = 0;
    dp[i] = Infinity;
    for (let j = i; j >= 1; 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];
}

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int width = 0, height = 0;
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j >= 1; 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];
    }
}

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

Explanation

Books must stay in their given order, so the only real decision is where each shelf ends. We solve it with a 1D DP where dp[i] means "the smallest total height needed to place the first i books."

To compute dp[i], we imagine the last shelf. That shelf must end with book i-1, but it can start at any earlier book as long as their combined thickness fits within shelfWidth. We try every such starting point.

The inner loop walks backwards from book i, adding thicknesses into width and tracking the tallest book in height. As long as width <= shelfWidth, the cost of this choice is dp[j - 1] + height: the best height for everything before this shelf, plus this shelf's own height. We keep the minimum.

Example: books = [[1,3],[2,4],[3,2]], shelfWidth = 6. All three fit on one shelf (thickness 1+2+3 = 6), so the height is just the tallest book, 4. Splitting them would add extra shelf heights, so 4 wins.

Once we filled the table from left to right, dp[n] holds the answer.

Time: O(n²) Space: O(n)