Ph.D. Qual Study Assistant

Book Shelving Problem

1. The Problem

Given `n` books in a fixed order, each with a thickness `t_i` and height `h_i`, we need to place them on shelves of a fixed length `L`. The height of each shelf adjusts to fit the tallest book placed on it. The goal is to find an arrangement that minimizes the total height of all shelves used.

2. The Idea: Dynamic Programming

This is an optimal partitioning problem. The arrangement of the first `i` books must contain an optimal arrangement for some smaller number of books, `j-1`, plus one final shelf containing books `j` through `i`.

Let `dp[i]` be the minimum total height required to shelve the first `i` books (from book 1 to book `i`). Our objective is to find `dp[n]`.

  • Base Case: The cost to shelve zero books is zero. `dp[0] = 0`.
  • Recurrence Relation: To compute `dp[i]`, we consider all possibilities for the last shelf. The last shelf could contain books `j` through `i` (where `1 <= j <= i`). For each possible `j`, if books `j` through `i` fit on one shelf, we can calculate the cost: it would be the minimum cost for the first `j-1` books (`dp[j-1]`) plus the height of this new shelf (which is `max(h_k)` for `k` from `j` to `i`). We choose the `j` that gives the minimum total height.
dp[i] = min_{1 ≤ j ≤ i} ( dp[j-1] + max_{j ≤ k ≤ i}(h_k) )

This is subject to the constraint that the sum of thicknesses from `j` to `i` does not exceed `L`.

3. The Algorithm

  1. Create a DP array `dp` of size `n+1`. Initialize `dp[0] = 0` and `dp[i] = infinity` for `i > 0`.
  2. Create a `path` array to reconstruct the solution.
  3. Outer loop for `i` from 1 to `n` (the number of books to consider).
  4. Inner loop for `j` from `i` down to 1 (the start of the last shelf).
    • In this inner loop, maintain `current_thickness` and `current_max_height` for books `j` through `i`.
    • If `current_thickness <= L`:
      • Calculate the potential new total height: `cost = dp[j-1] + current_max_height`.
      • If `cost < dp[i]`, update `dp[i] = cost` and `path[i] = j-1`.
    • Else, break the inner loop (since adding more books will only exceed `L`).
  5. The minimum total height is `dp[n]`. The shelf arrangement can be found by backtracking using the `path` array.

4. Complexity Analysis

Time Complexity: O(n²)
The algorithm has two nested loops. The outer loop (`i`) runs `n` times. The inner loop (`j`) also runs up to `n` times. Inside the inner loop, the calculations for `current_thickness` and `current_max_height` are done in O(1) time per step. This leads to a total time complexity of O(n²).
Space Complexity: O(n)
We use a DP array `dp` and a `path` array, both of size `n+1`, which requires O(n) auxiliary space.

Algorithm Visualization