'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List

'''
For dp[i+1],
either place book i on a new shelve => dp[i] + height[i],
or grab previous books together with book i and move to 
next level together, utlitzing the sub problem dp[j] 
=> min(dp[j] + max(height[j+1] .. height[i])), 
where sum(width[j+1] + ... + sum(width[i]) <= shelve_width
######
1. Start placing books one by one, always use a new shelve to begin with
2. After you stored the new height value at this position in your dp 
array, start looking back at previous books one by one, and see 
while the width permits, how many books you can fit on this new level.
3. Check to see if bringing said books down reduced the overall height,
if it did, update the new loest height value at your dp array.
          
'''
class Solution:
    # dp, O(n^2) for T and O(n) for S
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        n = len(books)
        # dp[i] stands for:
        # min height for books[0] ~ books[i - 1]
        dp = [float('inf')]* (n+1)
        dp[0] = 0 # no book, no height
        for i in range(1, n+1): # bottom up
            # trying to get dp[i] (books[i-1])
            curWidth = books[i-1][0]
            curHeight = books[i-1][1]
            dp[i] = dp[i-1] + curHeight # meaning build a new level for books[i-1]
            # now let's check whether put previous books with books[i-1] could optimize the situation
            for j in range(i-1, 0, -1):
                curWidth += books[j - 1][0]
                if curWidth > shelf_width:
                    break
                curHeight = max(curHeight, books[j-1][1])
                dp[i] = min(dp[i], dp[j-1] + curHeight)
        return dp[-1]

sol = Solution()
sol.minHeightShelves([[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], 4)                   