发表于 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 题目链接