Filling Bookcase Shelves LeetCode solution in Python

1
class Solution:
2
    def minHeightShelves(self, books, shelf_width: int) -> int:
3
        n, dp = len(books), [float("inf")] * (len(books) + 1)
4
        dp[0] = 0
5

6
        for i in range(1, n + 1):
7
            max_width, max_height, j = shelf_width, 0, i - 1
8

9
            while j >= 0 and max_width - books[j][0] >= 0:
10
                max_width -= books[j][0]
11
                max_height = max(max_height, books[j][1])
12
                dp[i] = max_height
13
                j -= 1
14

15
            if j >= 0 and max_width - books[j][0] < 0:
16
                j = i - 1
17
                dp[i] = float("inf")
18
                width, height = 0, 0
19
                while j >= 0 and width + books[j][0] <= shelf_width:
20
                    width = width + books[j][0]
21
                    height = max(books[j][1], height)
22
                    dp[i] = min(dp[i], height + dp[j])
23
                    j -= 1
24

25
        return dp[n]