Участник:Никита Плетнев/filling bookcase shelves

Материал из DISCOPAL
Перейти к: навигация, поиск

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, {})