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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

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:
		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
			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]], 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
			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)
		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]


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:
					break
				height = max(height, h)
				others = helper(i + 1)
				out = min(height + others, out)
				i += 1
			return out
		out = helper(0)
		return out


class Solution:

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

		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
				if cur_w + w <= shelf_width:
					if cur_h > 0 and h - cur_h >= 2:
						pass
					else:
						shelf.append((w, h))
						added = True
				if not added:
					shelf = [(w, h)]
					shelves.append(shelf)
			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:
		pass

	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:
				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]