Medium

题目描述

给定一个数组 books，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。另外给定一个整数 shelfWidth。

我们想要把这些书按顺序放到书架上，书架的宽度为 shelfWidth。

我们选择一些书放在这一层书架上，使得它们厚度的总和小于等于 shelfWidth，然后建造书架的下一层，使得书架的总高度增加我们刚刚放下的书中的最大高度。重复这个过程，直到没有更多的书要放置。

注意，在上述过程的每一步中，我们放置书籍的顺序与给定的书籍序列顺序相同。

例如，如果我们有一个有序的 5 本书的列表，我们可能把第一本和第二本书放在第一层书架上，第三本书放在第二层书架上，第四本和第五本书放在最后一层书架上。

返回按这种方式放置书架后，书架可能的最小总高度。

示例 1：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6。
注意，第 2 本书不一定要放在第一层书架上。

示例 2：

输入：books = [[1,3],[2,4],[3,2]], shelfWidth = 6
输出：4

提示：

  • 1 <= books.length <= 1000
  • 1 <= thicknessi <= shelfWidth <= 1000
  • 1 <= heighti <= 1000

解题思路

这是一个经典的动态规划问题，关键在于理解书籍必须按顺序放置的约束条件。

核心思路： 定义 dp[i] 表示放置前 i 本书所需的最小高度。对于第 i 本书，我们需要决定从哪一本书开始和第 i 本书放在同一层。

状态转移：

  1. 遍历每个位置 i，考虑第 i 本书可能的放置方案
  2. 从位置 j 到位置 i 的书籍如果能放在同一层（总厚度 ≤ shelfWidth），则可以更新 dp[i+1]
  3. 状态转移方程：dp[i+1] = min(dp[i+1], dp[j] + maxHeight(j, i))

其中 maxHeight(j, i) 表示从书籍 j 到书籍 i 中的最大高度。

算法步骤：

  1. 初始化 dp 数组，dp[0] = 0（没有书时高度为0）
  2. 对于每个位置 i，向前查找能够放在同一层的书籍
  3. 在满足宽度约束的前提下，计算该层的最大高度
  4. 更新 dp[i+1] 为所有可能方案中的最小值

时间复杂度为 O(n²)，空间复杂度为 O(n)，这是一个高效的解法。

代码实现

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            int width = 0, height = 0;
            for (int j = i; j >= 0; j--) {
                width += books[j][0];
                if (width > shelfWidth) break;
                height = max(height, books[j][1]);
                dp[i + 1] = min(dp[i + 1], dp[j] + height);
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(n):
            width = height = 0
            for j in range(i, -1, -1):
                width += books[j][0]
                if width > shelfWidth:
                    break
                height = max(height, books[j][1])
                dp[i + 1] = min(dp[i + 1], dp[j] + height)
        
        return dp[n]

public class Solution {
    public int MinHeightShelves(int[][] books, int shelfWidth) {
        int n = books.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            int width = 0, height = 0;
            for (int j = i; j >= 0; j--) {
                width += books[j][0];
                if (width > shelfWidth) break;
                height = Math.Max(height, books[j][1]);
                dp[i + 1] = Math.Min(dp[i + 1], dp[j] + height);
            }
        }
        
        return dp[n];
    }
}

var minHeightShelves = function(books, shelfWidth) {
    const n = books.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 0; i < n; i++) {
        let width = 0, height = 0;
        for (let j = i; j >= 0; j--) {
            width += books[j][0];
            if (width > shelfWidth) break;
            height = Math.max(height, books[j][1]);
            dp[i + 1] = Math.min(dp[i + 1], dp[j] + height);
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 n 次，内层循环最多 n 次
空间复杂度O(n)需要 dp 数组存储状态