# code tpl

{%hackmd theme-dark %}

1105. Filling Bookcase Shelves

> You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.
> We want to place these books in order onto bookcase shelves that have a total width shelfWidth.


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

[[1,1],[2,3],[2,3]]

-------A X
[1] [2] 3
    [3] 3
    
------B O
[1] 1
[2] [3] 3

dp[1-4] = 
dp[1-3] + max(4) 
or dp[1-2] + max(3, 4) +  
or dp[1-1] + max(2, 3, 4)


dp[1-3] = 
max(1) + dp[2-4]
or max(1, 2) + dp[3-4]
or max(1, 2, 3) + dp[4]

dfs(book, i, total_width, maxH)
if totalw + book[i] < selvew
maxH = max(book_h, maxH);
maxH+ dfs(book, i+, totalw - book[i])

dfs(book, i+1, selve_width, )

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 is 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

###### tags: `mock interview` `面試`