題目網址：https://leetcode.cn/problems/filling-bookcase-shelves/

題意：給一整數 array books,其中 books[i] = [thickness_i, height_i] 表示第 i 本書的厚度和高度。且會得到一個整數 shelfWidth。

按順序將這些書擺放到總寬度為 shelfWidth 的書架上。

先選幾本書放在書架上（它們的厚度之和小於等於書架的寬度 shelfWidth）, 然後再建一層書架。重覆這個過程, 直到把所有的書都放在書架上。

需要注意的是, 在上述過程的步驟中, 擺放書的順序須與整理好的順序相同。

  • 例如, 如果有 5 本書, 那麼可能的一種擺放情況是：第一和第二本書放在第一層書架上, 第三本書放在第二層書架上, 第四和第五本書放在最後一層書架上。

返回以這種方式布置書架的最小高度。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 books 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i]：代表 books[1:i] 中布置書架的最小高度

2. 得到轉移方程：

  • 若 sum(books[j:i].width) ≤ shelfWidth, 則將 books[j:i] 放在同一層, 並更新當前層的最大高度 height, 則 dp[i] 可由上一層建構而來
    ➔ 故 dp[i] = max(dp[i], dp[j - 1] + height), 其中 1 ≤ j < i

3. 初始化：

  • dp[0]：沒有書的書架, 其書架的最小高度為 0
  • dp[1]：只有一本書的書架, 其書架的最小高度為 books[1].height
cpp
class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        const int n = books.size();
        vector<int> dp(n + 1, 0);

        books.emplace(books.begin(), vector<int>{0, 0});
        dp[1] = books[1][1];

        for (int i = 2; i <= n; ++i) {
            int width = books[i][0], height = books[i][1];
            dp[i] = dp[i - 1] + height; // 初始化 dp[i] : 將 books[i] 放到下一層

            for (int j = i - 1; j > 0; --j) { // 由於同一層是連續的, 所以從 i - 1 倒推
                // books[i], books[j] 在同一層
                width += books[j][0];

                if (width > shelfWidth) {
                    break;
                }

                height = max(height, books[j][1]); // 更新當前層的最大高度
                dp[i] = min(dp[i], dp[j - 1] + height); // 注意是 j - 1, 因為 i, j 同層
            }
        }

        return dp.back();
    }
};
  • time：O(n2) ➔ for loop
  • space：O(n) ➔ dp