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

Difficulty: interview

Starter code:

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        

Solutions:
class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        n = len(books)
        dp = [inf] * (n+1)
        dp[0] = 0
        ret = inf
        for i in range(1, n+1):
            mx = 0
            cur = 0
            for j in range(i, 0, -1):
                cur += books[j-1][0]
                if cur > shelf_width:
                    break
                mx = max(mx, books[j-1][1])
                dp[i] = min(dp[i], dp[j-1] + mx)
        return dp[-1]


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        dp = [0]*(len(books)+1)
        for i in range(len(books)):
            maxheight = books[i][1]
            height = dp[i] + books[i][1]
            width = books[i][0]
            j = i-1
            while j >= 0 and width + books[j][0] <= shelf_width:
                maxheight = max(maxheight,books[j][1])
                width += books[j][0]
                height = min(height,dp[j]+maxheight)
                j -= 1
            dp[i+1] = height
        print(dp)
        return dp[-1]


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        if not books:
            return 0
        h = [0]
        current = 0
        while current < len(books):
            w = books[current][0]
            f = current
            c_h = books[current][1]
            h_i = float('inf')
            while w <= shelf_width and f >=0:
                
                h_i = min(c_h + h[f], h_i) 
                if f == 0:
                    break
                f-=1
                w+= books[f][0]
                c_h = max(c_h, books[f][1])
            h.append(h_i)
            
            current += 1

        return h[-1]
        


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        n = len(books)
        heights = [0 for _ in range(n+1)]
        
        for i in range(1, n+1):
            width  = books[i-1][0]
            height = books[i-1][1]
            heights[i] = heights[i-1] + height
            j = i-1
            while j > 0 and width + books[j-1][0] <= shelf_width:
                height = max(height, books[j-1][1])
                width+=books[j-1][0]
                heights[i] = min(heights[i], heights[j-1] + height)
                j-=1
        print(f'{heights}')
        return heights[-1]


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        # Index 0 is for 0 books
        subsoln = [0 for _ in range(len(books) + 1)]
        
        for prev_idx, (w, h) in enumerate(books):
            cur_idx = prev_idx + 1
            subsoln[cur_idx] = subsoln[prev_idx] + h
            
            cur_w = w
            cur_h = h
            # Take book from previous shelf and see if it's better.
            while prev_idx >= 1 and cur_w + books[prev_idx-1][0] <= shelf_width:
                cur_h = max(cur_h, books[prev_idx-1][1])
                cur_w += books[prev_idx-1][0]
                subsoln[cur_idx] = min(subsoln[cur_idx], subsoln[prev_idx-1] + cur_h)
                prev_idx -= 1
        print(subsoln)
            
            
        return subsoln[-1]

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        
        books_len = len(books)
        
        @lru_cache(None)
        def dp(i):
            if i == books_len:
                return 0
            
            width, height, result = 0, 0, float('inf')
            
            while i < books_len and width <= shelf_width:
                width += books[i][0]
                height = max(height, books[i][1])
                if width <= shelf_width:
                    result = min(result, height + dp(i+1))
                i += 1
            
            return result
        
        return dp(0)

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        @lru_cache(None)
        def dp(i):
            if i == 0: return books[0][1]                        
            max_height, thickness, ans = -float('inf'), 0, float('inf')            
            for j in range(i, -1, -1):
                t, h = books[j]
                if thickness + t <= shelf_width:
                    thickness += t
                    max_height = max(max_height, h)                                    
                    ans = min(ans, (dp(j-1) + max_height) if j > 0 else max_height)
                else: break
            return ans                
        n = len(books)
        for i in range(n): dp(i)
        return dp(n-1)

\"\"\"

\"\"\"

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        
        books_len = len(books)
        
        @lru_cache(None)
        def dp(i):
            if i == books_len:
                return 0
            
            width, height = 0, 0
            
            result = []
            
            while i < books_len and width <= shelf_width:
                width += books[i][0]
                height = max(height, books[i][1])
                if width <= shelf_width:
                    result.append(height + dp(i+1))
                i += 1
            
            return min(result)    
        
        return dp(0)

class Solution:
    def minHeightShelves(self, books: List[List[int]], sw: int) -> int:
        n = len(books)
        mem = [None] * (n + 1)
        mem[-1] = 0
        
        def f(pos):
            if mem[pos] is not None:
                return mem[pos]
            
            w, h = 0, 0
            value = float('inf')
            
            for i in range(pos, n):
                w += books[i][0]
                h = max(h, books[i][1])
                if w > sw:
                    break
                value = min(value, f(i + 1) + h)
            
            mem[pos] = value
            return mem[pos]
            
        
        return f(0)

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        memo = [float('inf')] * (len(books)+1)
        memo[0] = 0
        
        for i in range(len(books)):
            width = shelf_width
            height = 0 
            j = i
            # to determine the minimum height up to the ith book, 
            # we need te examine all possible books which in the same level as the ith book up to the ith book
            # the later books which may be in the same level as the ith book will be examined later when it is introduced.
            while j >=0 and width - books[j][0]>=0:      
                width -= books[j][0]
                height = max(height, books[j][1])
                memo[i+1] = min(memo[i+1], memo[j]+height)
                j -= 1
        
        return memo[-1]

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        # n = len(books)
        # @lru_cache(None)
        # def dfs(i, w, h):
        #     if i >= n:
        #         return h
        #     return min(h + dfs(i + 1, books[i][0], books[i][1]), float('inf') if w + books[i][0] > shelf_width else dfs(i + 1, w + books[i][0], max(h, books[i][1])))
        # return dfs(0, 0, 0)
        
        n = len(books)
        dp = [0] + [float('inf')] * n
        for p in range(1, n + 1):
            i = p
            w = h = 0
            while i > 0 and w + books[i-1][0] <= shelf_width:
                w += books[i-1][0]
                h = max(h, books[i-1][1])
                dp[p] = min(dp[p], dp[i-1] + h)
                i -= 1
        return dp[-1]
        
        
        # n = len(books)
        # dp = [0] + [float('inf')] * n
        # for p in range(1, n + 1):
        #     i = p
        #     w = h = 0
        #     while i > 0 and w + books[i-1][0] <= shelf_width:
        #         w += books[i-1][0]
        #         h = max(h, books[i-1][1])
        #         dp[p] = min(dp[p], dp[i-1]+h)
        #         i -= 1
        # return dp[-1]
        
        # n = len(books)
        # @lru_cache(None)
        # def dfs(i, w, h):
        #     if i >= n:
        #         return h
        #     return min(h + dfs(i + 1, books[i][0], books[i][1]), float('inf') if w + books[i][0] > shelf_width else dfs(i + 1, w + books[i][0], max(h, books[i][1])))
        # return dfs(0, 0, 0)
    
                
            


import math
class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        n = len(books)
        dp = [math.inf]*(n+1)
        dp[0] = 0
        for i in range(1,n+1):
            max_width = shelf_width
            max_height = 0
            j = i-1
            while j>=0 and max_width - books[j][0] >= 0:
                max_width -= books[j][0]
                max_height = max(max_height, books[j][1])
                dp[i] = min(dp[i], dp[j] + max_height)
                j -= 1
        return dp[n]

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        self.shelf = defaultdict(list)
        
        @lru_cache(None)
        def helper(i):
            if i == len(books):
                return 0
            
            width = 0
            height = 0
            out = float('inf')            
            
            while width < shelf_width and i < len(books):
                w,h = books[i]                
                width += w
                
                if width > shelf_width: # went over when added this new book
                    break
                    
                # max height of this shelf with new book added
                height = max(height, h) 
                
                # see how much the total height others are if we include the new book
                # in this shelf
                others = helper(i+1) 
                
                # if height of current shelf+ total height of other books is minimum
                # save it.
                out = min(height+others, out) 
                i+= 1
            return out
        
        out = helper(0)
        return out
            
            


def go_bf(i, books, curr_width, ch, shelf_width):
    if i == len(books):
        return 0

    w,h = books[i][0], books[i][1]
    best_h = float(\"inf\")
    if curr_width + w <= shelf_width:
        # if we add higher then we pay, is smaller then it's for free
        diff = max(h - ch, 0)   
        best_h = diff + go_bf(i+1, books, curr_width + w, ch, shelf_width)
    best_h = min(best_h, h + min(best_h, go_bf(i+1, books, w, h, shelf_width)))
    return best_h

def go_memo(i, books, curr_width, ch, shelf_width, memo):
    if i == len(books):
        return 0

    if memo[i][curr_width] == -1:
        w,h = books[i][0], books[i][1]
        best_h = float(\"inf\")
        if curr_width + w <= shelf_width:
            # if we add higher then we pay, is smaller then it's for free
            diff = max(h - ch, 0)   
            best_h = diff + go_memo(i+1, books, curr_width + w, ch + diff, shelf_width, memo)
        best_h = min(best_h, h + min(best_h, go_memo(i+1, books, w, h, shelf_width, memo)))
        memo[i][curr_width] = best_h
    return memo[i][curr_width]

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        memo = [[-1] * (shelf_width + 1) for _ in range(len(books))]
        return go_memo(0, books, 0, 0, shelf_width, memo)

min_high_dict = {}

def minHigh( cw, mw, arr, ch):
    
    try:
        if min_high_dict[str(cw) +\" \" + str(len(arr))] != None:
            return min_high_dict[str(cw) +\" \" + str(len(arr))] 
    except KeyError:
        pass
    
    if len(arr) == 0:
        return ch
    
    elif cw == mw:
        re = max( arr[0][1], minHigh( cw-arr[0][0], mw, arr[1:], arr[0][1]))
    
    elif cw >= arr[0][0]:
        re1 = max( max(ch,arr[0][1]), minHigh( cw - arr[0][0], mw, arr[1:], max(ch,arr[0][1])))
        re2 = ch + minHigh( mw - arr[0][0], mw, arr[1:], arr[0][1])
        re = min( re1, re2)
    
    else:
        re = ch + minHigh( mw - arr[0][0], mw, arr[1:], arr[0][1])
    
    min_high_dict[str(cw) +\" \" + str(len(arr))] = re
    return re
    
class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        min_high_dict.clear()
        return minHigh( shelf_width, shelf_width, books, 0)

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        
        # chanllenge is when to switch to new level
        
        def naive(books, shelf_width, remain=None):
            if remain is None:
                remain = shelf_width
            shelf = []
            shelves = [shelf]
            for w,h in books:
                cur_w = sum(x for x,y in shelf)
                cur_h = max((y for x,y in shelf), default=0)
                added = False
                # print((w,h), cur_w, cur_h)
                if cur_w + w <= shelf_width:
                    if cur_h > 0 and h - cur_h >= 2:  # do some lookahead
                        pass
                    else:
                        shelf.append((w,h))
                        added = True
                if not added:
                    shelf = [(w,h)]
                    shelves.append(shelf)
                # print('levels:', len(shelves), sum(max((y for x,y in s), default=0) for s in shelves), shelves)
            return sum(max(y for x,y in s) for s in shelves)
        
        return naive(books, shelf_width)
        
        
    def minHeightShelves1(self, books: List[List[int]], shelf_width: int) -> int:
        # put the highest books first
        pass
    
    
    # https://leetcode.com/problems/filling-bookcase-shelves/discuss/323350/Python-Clean-DP-Solution-2D-Knapsack
    # It's a kind of 2D knapsack problem.
    # The core recurrence function is dp[i+1] = min(dp[k] + h for k in {j+1,...,i}).

    # j is the furthest index that {books[j+1],...,books[i]} can be placed in one row.
    # It depends on the widths of those books. books[j] can't be placed into the same row with books[i]
    # otherwise the width would exceed the shelf_width.
    # k is each candidate index that {{books[k],...,books[i]}} are proposed to be placed in the same row.
    # h is the maximum height among {books[k],...,books[i]}.

    def minHeightShelves(self, books, shelf_width):
        def height(i, j):
            return max(books[x][1] for x in range(i,j))
            
        dp = [0]
        for i in range(len(books)):
            w, j = books[i][0], i
            while j >= 0 and w <= shelf_width:     # find out j, so w should be ahead of j
                j -= 1
                w += books[j][0] 
            dp.append(min(dp[k] + height(k,i+1) for k in range(j+1,i+1)))
        return dp[-1]

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
        nums = len(books)
        dp = [0 for _ in range(nums+1)]
        for i in range(nums):
            height = books[i][1]
            width = books[i][0]
            dp[i+1] = dp[i] + height
            for j in range(i)[i::-1]:
                print(i,j)
                if width + books[j][0] <= shelf_width:
                    height  = max(height, books[j][1])
                    dp[i+1]= min(height + dp[j], dp[i+1])    
                    width = width + books[j][0]
                else:
                    break
            print(f\"ans{dp[i+1]}\")
        return dp[-1]