Problem Explanation

We're given a sequence of n books, each with a specified thickness and height. The task is to shelve these books onto a bookcase of a particular width, such that the total height of the bookcase is minimized. This is subject to the condition that the books must be placed on shelves in the same order they're given, and a shelf can hold as many books as can fit (i.e., the sum of thicknesses is less than or equal to the shelf's width).

Example Walkthrough

Consider the example books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]] and shelf_width = 4.

We could first place the book of dimensions [1,1] onto the first shelf. Then place the next two books [2,3],[2,3] onto the second shelf (as their total thickness 4 is not greater than shelf_width). Repeat the process placing the next three books [1,1],[1,1],[1,1] onto the third shelf and the last book [1,2] onto the fourth.

After adding up the maximum height of each shelf, the total height of the bookcase is 1+3+1+2=7.

However, if we rearrange the books a bit, placing the first two books [1,1],[2,3] onto the first shelf, the next three books [2,3],[1,1],[1,1] onto the second, and the last two books [1,1],[1,2] onto the third, we get a total height of 1+3+2=6. This solution is optimal hence would be our output.

Solution Approach

The solution starts by initializing a dynamic programming (dp) array dp with a size of n+1 (n being the total number of books) and filled with a large value (INT_MAX). dp[i] aims at storing the minimum total height to place the first i books. The base case dp[0] is set as 0 since no height is needed when placing zero books.

Next, we iterate over the books. For each book i, we try to see if placing books i to j (i >= j >= 0) onto a new shelf results in an optimal solution. The sum of thicknesses of these books is cumulated in sumThickness and the greatest height is tracked in maxHeight. We break the loop when sumThickness > shelfWidth as placing the current book leads to an oversized shelf. The optimal height after placing the i-th book is updated as min(dp[i+1], dp[j] + maxHeight). This line translates to comparing the result of two operations:

• placing the book i onto a new shelf: the height increases by the maximum height of books located between j and i.
• not shelving the book i: the total height remains the same (i.e., dp[i+1]).

The process is repeated until all books are examined. The final value in dp (dp.back() in C++) holds the least height to place all books in order.

Python Solution

1
2python
3class Solution:
4    def minHeightShelves(self, books, shelf_width):
5        dp = [0] + [float('inf')] * len(books) 
6        for i in range(len(books)):
7            width, j = 0, i
8            tallest = 0
9            while j >= 0 and width + books[j][0] <= shelf_width:
10                height, thickness = books[j]
11                width += thickness
12                tallest = max(tallest, height)
13                dp[i+1] = min(dp[i+1], dp[j] + tallest)
14                j -= 1
15        return dp[-1]

Here float('inf') represents an infinity (a large number that's greater than any other number), and dp[-1] fetches the last element in the dp list (same as dp.back() in C++).

Java Solution

1
2java
3class Solution {
4    public int minHeightShelves(int[][] books, int shelf_width) {
5        int n = books.length;
6        int[] dp = new int[n+1];
7        dp[0] = 0;
8        for(int i = 1; i <= n; i++){
9            int width = books[i-1][0];
10            int height = books[i-1][1];
11            dp[i] = dp[i-1] + height;
12            for(int j = i-1; j > 0 && width + books[j-1][0] <= shelf_width; j--){
13                height = Math.max(height, books[j-1][1]);
14                width += books[j-1][0];
15                dp[i] = Math.min(dp[i], dp[j-1] + height);
16            }
17        }
18        return dp[n];
19    }
20}

JavaScript Solution

1
2javascript
3var minHeightShelves = function(books, shelf_width) {
4    const dp = Array(books.length + 1).fill(Number.MAX_SAFE_INTEGER);
5    dp[0] = 0;
6    for(let i=0; i<books.length; i++) {
7      let width = 0;
8      let maxHeight = 0;
9      for(let j=i; j>=0; j--) {
10        const [thickness, height] = books[j];
11        width += thickness;
12        if(width > shelf_width) break;
13        maxHeight = Math.max(maxHeight, height);
14        dp[i+1] = Math.min(dp[i+1], dp[j] + maxHeight);
15      }
16    }
17    return dp[dp.length-1];
18};

This javascript solutionn uses MAX_SAFE_INTEGER a constant in JavaScript to represent maximum numeric value possible in JavaScript.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
6        vector<int> dp(books.size() + 1, INT_MAX);
7        dp[0] = 0;
8        for (int i = 0; i < books.size(); ++i) {
9            int width = 0;
10            int height = 0;
11            for(int j = i; j >=0; --j) {
12                width += books[j][0];
13                height = max(height, books[j][1]);
14                if(width > shelf_width)
15                    break;
16                dp[i+1] = min(dp[i+1], dp[j] + height);
17            }
18        }
19        return dp.back();
20    }
21};

This C++ uses INT_MAX, a constant in C++ that returns the maximum value that can be hold by an integer.

C# Solution

1
2csharp
3public class Solution {
4    public int MinHeightShelves(int[][] books, int shelf_width) {
5        int n = books.Length;
6        int[] dp = new int[n+1];
7        dp[0] = 0;
8        for(int i = 1; i <= n; i++){
9            int width = books[i-1][0];
10            int height = books[i-1][1];
11            dp[i] = dp[i-1] + height;
12            for(int j = i-1; j > 0 && width + books[j-1][0] <= shelf_width; j--){
13                height = Math.Max(height, books[j-1][1]);
14                width += books[j-1][0];
15                dp[i] = Math.Min(dp[i], dp[j-1] + height);
16            }
17        }
18        return dp[n];
19    }
20}

In all these solutions, time complexity is O(n^2) because we have nested for loop running n times each, and the space complexity is O(n) for the DP array. This algorithm can be considered a variation of the Knapsack problem which is a common problem in combinatorial optimization.## Ruby Solution

1
2ruby
3class Solution
4  def minHeightShelves(books, shelf_width)
5    dp = Array.new(books.length + 1, Float::INFINITY)
6    dp[0] = 0
7    books.each_with_index do |book, i|
8      width, max_height = 0, 0
9      j = i
10      while j >= 0 && width + books[j][0] <= shelf_width
11        width += books[j][0]
12        max_height = [max_height, books[j][1]].max
13        dp[i+1] = [dp[i+1], dp[j] + max_height].min
14        j -= 1
15      end
16    end
17    dp[-1]
18  end
19end

This Ruby solution uses Float::INFINITY to represent an extremely large positive number which suffices for a sufficiently high initial height of shelves. Iterating from the back, for each book, we try to fit it onto the same shelf as the previous one and keep track of the current width and the maximum height. The ternary [max_height, books[j][1]].max is an equivalent for Math.max() in other languages and the ternary [dp[i+1], dp[j] + max_height].min is equivalent to Math.min().

Finally, when we have gone through all the books, the smallest total height is stored in dp[-1]. With the time complexity of O(n^2) and space complexity of O(n), this forward-thinking dynamic programming solution is efficient for the problem.

Wrapping Up

Now with solutions in Python, Java, JavaScript, C++, C# and Ruby, you have multiple perspectives to solving this problem. It involves careful arrangement of the given books, each with a different height and thickness, onto the shelves making sure the given order is maintained.

Remember, when solving such dynamic programming problems the key is to articulate the base case and logic for optimal substructure correctly. Once you've got the hang of these aspects, coding the solutions should fall into place with enough practice! Happy coding!