JZX轻语：简

LeetCode 1105 - 填充书架

发表于2024年06月14日

#动态规划

放置/分类且求某最小值的题目，可以考虑动态规划。本题中使用dp[i]表示放置前i本书所需的最小高度。在遍历书i时，需要考虑最后一层 + 前面层的最小值，可以遍历书i放在最后一层的所有可能情况，计算当前情况的总高度(最后一层高度+前面层次的高度，后者可以直接取上一层最后一本书的dp结果)，取其中的最优解(因此就满足了最优子结构)。状态转移方程为dp[i] = min(dp[j] + line_height)，其中j为上一层最后一本书的编号(j < i)，且sum(width[j+1..i]) <= shelf_width，line_height为最后一层的高度(j+1到i之间的最大值)。

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        dp = [0] * len(books)
        for i in range(len(books)):
            level_load = books[i][0]
            level_height = books[i][1]
            level_books = 1

            while level_load <= shelfWidth and level_books <= i + 1:
                height = (dp[i - level_books] if i - level_books >= 0 else 0) + level_height 
                if dp[i] == 0 or dp[i] > height:
                    dp[i] = height

                # update
                level_load += books[i - level_books][0]
                level_height = max(level_height, books[i - level_books][1])
                level_books += 1
        return dp[-1]

闪念标签：LC

题目链接：https://leetcode.cn/problems/filling-bookcase-shelves/