Problem statement

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

Solution

Similar to Leetcode 1043. Partition Array for Maximum Sum, use dp here: dp[i] is the answer for the first i books. On each step we can try to choose last several books and check that their total width is <= W.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def minHeightShelves(self, A, W):
        n = len(A)
        dp = [0] + [float("inf")] * n
        for i in range(1, n + 1):
            curMax, width = 0, 0
            for k in range(i):
                curMax = max(curMax, A[i - k - 1][1])
                width += A[i - k - 1][0]
                if width > W: break
                dp[i] = min(dp[i], dp[i - k - 1] + curMax)
        
        return dp[-1]