1105. Filling Bookcase Shelves #

Problem #

We have a sequence of books: the i-th book has thickness books[i][0]and height books[i][1].

We want to place these books in order onto bookcase shelves that have total width shelf_width.

We choose some of the books to place on this shelf (such that the sum of their thickness is <= shelf_width), then build another level of shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note again that at each step of the above process, the order of the books we place is the same order as the given sequence of books. For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves are 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Constraints:

1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

Problem Summary #

A nearby furniture mall is having a promotion, and you bought the adjustable bookcase you have always wanted, planning to organize all your books onto the new bookcase. You have arranged the books to be placed, books, into a stack: from top to bottom, the thickness of the i-th book is books[i][0], and its height is books[i][1]. Place these books in order onto shelves with total width shelf_width.

First choose several books to place on a shelf (the sum of their thicknesses is less than or equal to the shelf width shelf_width), then build another level of shelf. Repeat this process until all books have been placed on the shelves.

It should be noted that in each step of the above process, the order in which the books are placed is the same as the order you arranged them in. For example, if there are 5 books here, one possible placement is: the first and second books are placed on the first shelf, the third book is placed on the second shelf, and the fourth and fifth books are placed on the last shelf. The maximum height of the books placed on each level is the height of that shelf level, and the overall height of the bookcase is the sum of the heights of all levels. Arrange the bookcase in this way and return the minimum possible overall height of the bookcase.

Solution Approach #

Given an array, each element in the array represents the width and height of a book. The books must be placed onto shelves of width shelf_width in the order of the books. Ask for the minimum height of the bookcase after all books have been placed.
The solution idea for this problem is dynamic programming. dp[i] represents the minimum height of the bookcase needed to place the first i books. The initial value is dp[0] = 0, and the others are the maximum value 1000*1000. Iterate through each book, treating the current book as the last book on the last shelf, and adjust the books before this one backward to see whether the previous shelf height can be reduced. The state transition equation is dp[i] = min(dp[i] , dp[j - 1] + h), where j represents the index of the books that can fit on the last shelf, and h represents the maximum height of the last shelf. After adjusting j once, the minimum height value of the bookcase can be found. The time complexity is O(n^2).

Code #


package leetcode

func minHeightShelves(books [][]int, shelfWidth int) int {
	dp := make([]int, len(books)+1)
	dp[0] = 0
	for i := 1; i <= len(books); i++ {
		width, height := books[i-1][0], books[i-1][1]
		dp[i] = dp[i-1] + height
		for j := i - 1; j > 0 && width+books[j-1][0] <= shelfWidth; j-- {
			height = max(height, books[j-1][1])
			width += books[j-1][0]
			dp[i] = min(dp[i], dp[j-1]+height)
		}
	}
	return dp[len(books)]
}