https://leetcode.com/problems/filling-bookcase-shelves/submissions/

class Solution: def solve(self, books, shelf_width, memory): if books == []: return 0 books_imm = tuple([tuple(x) for x in books]) if books_imm in memory: return memory[books_imm] width = 0 height = 0 stack = [] last_j = len(books) for j, book in enumerate(books): width += book[0] if width > shelf_width: last_j = j break if j > 0 and book[1] > height: stack.append((j, height)) if book[1] > height: height = book[1] min_height = height + self.solve(books[last_j:], shelf_width, memory) for j, h in stack: mh = h + self.solve(books[j:], shelf_width, memory) if mh < min_height: min_height = mh memory[books_imm] = min_height return min_height def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int: return self.solve(books, shelf_width, {})