# 1105. Filling Bookcase Shelves

# 20221017

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4

Output: 6

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

book = 1
--
1
--

book = 1, 2
--
1 2
--

book = 1 2 3
--     
1 2 -> 
--

--
1 2
--
3
--

or
******
--
1 
--
2 3
--
*****

dp[i]: minium height of book i to book n

dp[i-1] -> dp[i]

dp[2]
put book 2 onto shelf
1. new row for book

--
2
--

** determine dp[2] ** 
choice 1 -> dp[2] = H(2) + dp[3]
__
2
__

choice 2 -> dp[2] = max(H(2),H(3)) + dp[4]
__
2 3
__

choice 3 -> dp[2] = max(H(2),H(3),H(4)) + dp[5]
__
2 3 4
__


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        
        dp = [inf]*(len(books)+1)
        
        dp[0] = 0
        
        for i in range(1,len(books)+1):
            
            curWidth = shelfWidth
            curMaxHeight = 0
            j = i - 1
            while j >= 0 and curWidth >= books[j][0]:
                curMaxHeight = max(curMaxHeight, books[j][1])
                curWidth -= books[j][0]
                dp[i] = min(dp[i], dp[j] + curMaxHeight)
                j -= 1
                
        #print(dp)
        return dp[-1]