🔗 🟡 1105. Filling Bookcase Shelves 2014

tags: `Weekly Contest 143` `陣列(Array)` `動態規劃(DP)`

題意

給定一個二維整數陣列 $books$ ，其中 $books[i] = [thickness_i, height_i]$ 表示第 $i$ 本書的厚度和高度，令給定一個整數 $shelfWidth$ 表示書架的總寬度。

我們想按 照順序 把這些書放在書架上，書架的總寬度是 $shelfWidth$ 。

我們選擇一些書放在這個架子上，使得它們的厚度總和小於或等於 $shelfWidth$ ，然後再建一個書櫃的層，使得書櫃的總高度增加了我們剛剛放下的書的最大高度。我們重複這個過程，直到沒有書可放。

注意，在上述過程的每一步中，我們放書的順序與給定的書的順序相同。

例如，如果我們有 5 本書，我們可能會把第 $1$ 本和第 $2$ 本書放在第 $1$ 個架子上，第 $3$ 本書放在第 $2$ 個架子上，第 $4$ 本和第 $5$ 本書放在最後一個架子上。

返回在這種方式下放置書架後，書櫃的總高度的最小可能值。

思路：動態規劃(DP)

在這道題中，我們需要以最小高度來排列書本，而書架的寬度 $shelfWidth$ 限制了我們能在一層放置的書的總厚度，目標是最小化書櫃的總高度。

在放置了一些書之後，問題可以被遞迴到子問題，因此可以使用動態規劃(DP) 來解決這個問題。

方法一：選或不選

對於每本書，我們有兩種選擇：將其放在當前層 或者 將其放在新的一層。

因此可以定義一個遞迴函數 dfs(i, cur_w, cur_h) ，其中 i 表示當前書的編號，cur_w 表示當前層的寬度，cur_h 表示當前層的高度，轉移的方式分別為：

放到下一層：計算當前高度 $cur_h$ 加上剩下書本的最小高度，即 cur_h + dfs(i + 1, books[i][0], books[i][1])。
放到同一層：如果當前層的寬度允許，可以將當前書本放到同一層，更新當前層的寬度 $cur\_w$ 和高度 $cur\_h$ ，並遞迴計算後續書本的最小高度，即 dfs(i + 1, cur_w + books[i][0], max(cur_h, books[i][1]))。

遞迴終點發生在 i == n 時，即已經沒有書可放，我們可以直接返回 $0$ ，表示沒有書可放。

最終返回 dfs(0, 0, 0) 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n^2 \cdot m)$ $O (n^{2} \cdot m)$ ，其中 $n$ $n$ 是書本的數量、 $m$ $m$ 是書架的寬度 $shelfWidth$ $s h e l f Wi d t h$ 。
- 由於有 $n$ 本書、當前層的高度 $cur\_h$ 最多可能有 $n$ 種、當前層的寬度 $cur\_w$ 最多可能有 $m$ 種，因此總共有 $O(n^2 \cdot m)$ 個狀態，每個狀態需要 $O(1)$ 的時間進行轉移計算。
空間複雜度： $\mathcal{O}(n^2 \cdot m)$ ，即狀態數量。

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        @cache
        def dfs(i, cur_w, cur_h):
            if i == n:
                return cur_h
            res = cur_h + dfs(i + 1, books[i][0], books[i][1]) # 放到下一層
            if cur_w + books[i][0] <= shelfWidth: # 可以放到同一層
                res = min(res, dfs(i + 1, cur_w + books[i][0], max(cur_h, books[i][1])))
            return res
        return dfs(0, 0, 0)

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        vector<unordered_map<int, unordered_map<int, int>>> memo(n);
        function<int(int, int, int)> dfs = [&](int i, int cur_w, int cur_h) {
            if (i == n) return cur_h;
            if (memo[i].count(cur_w) && memo[i][cur_w].count(cur_h)) return memo[i][cur_w][cur_h];
            int res = cur_h + dfs(i + 1, books[i][0], books[i][1]); // 放到下一層
            if (cur_w + books[i][0] <= shelfWidth) { // 可以放到同一層
                res = min(res, dfs(i + 1, cur_w + books[i][0], max(cur_h, books[i][1])));
            }
            return memo[i][cur_w][cur_h] = res;
        };
        return dfs(0, 0, 0);
    }
};

方法二：枚舉當前層的最後一本書

在方法一中，我們需要維護當前層的寬度 $cur\_h$ 和高度 $cur\_w$ ，但我們可以直接考慮當前層的最後一本書，這樣就不用再維護這兩個變數了。

定義 dfs(i) 表示從第 $i$ 本書開始，排列完剩餘書本所需的最小高度。則可以依次枚舉當前層的最後一本書 $j$ ，並遞迴到子問題 dfs(j + 1)。

對於每一本書 $j$ ，我們嘗試將其放在當前層中，並維護一個變數 left_w ，表示剩餘的書架寬度，初始化為 $shelfWidth$ 。

如果第 $j$ 本書可以將其放在當前層中，將 max_h 更新為 $max\_h + j$ ，並更新答案，接著繼續考慮第 $j + 1$ 本書。
如果第 $j$ 本書不能將其放在當前層中，則不用繼續考慮第 $j + 1$ 本書，直接終止迴圈。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ $O (n^{2})$ ，其中 $n$ $n$ 是書本的數量。
- 總共有 $O(n)$ 個狀態，每個狀態需要 $O(n)$ 的時間進行轉移計算。
空間複雜度： $\mathcal{O}(n)$ ，即狀態數量。

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        @cache
        def dfs(i):
            if i == n:
                return 0
            res = float('inf')
            max_h, left_w = 0, shelfWidth
            for j in range(i, n):
                left_w -= books[j][0]
                if left_w < 0: # 無法將 books[i], ... , books[j] 放到同一層
                    break
                max_h = max(max_h, books[j][1]) # 更新最大高度
                res = min(res, max_h + dfs(j + 1)) # 遞迴到子問題
            return res
        return dfs(0)

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        vector<int> memo(n, -1);
        function<int(int)> dfs = [&](int i) {
            if (i == n) return 0;
            if (memo[i] != -1) return memo[i];
            int res = float('inf');
            int max_h = 0, left_w = shelfWidth;
            for (int j = i; j < n; ++j) {
                left_w -= books[j][0];
                if (left_w < 0) break; // 無法將 books[i], ... , books[j] 放到同一層
                max_h = max(max_h, books[j][1]); // 更新最大高度
                res = min(res, max_h + dfs(j + 1)); // 遞迴到子問題
            }
            return memo[i] = res;
        };
        return dfs(0);
    }
};