題目描述

附近的家居城促銷，你買回了一直心儀的可調(diào)節(jié)書架，打算把自己的書都整理到新的書架上。

你把要擺放的書 books 都整理好，疊成一摞：從上往下，第 i 本書的厚度為 books[i][0]，高度為 books[i][1]。

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

先選幾本書放在書架上（它們的厚度之和小于等于書架的寬度 shelf_width），然后再建一層書架。重復(fù)這個(gè)過程，直到把所有的書都放在書架上。

需要注意的是，在上述過程的每個(gè)步驟中，擺放書的順序與你整理好的順序相同。 例如，如果這里有 5 本書，那么可能的一種擺放情況是：第一和第二本書放在第一層書架上，第三本書放在第二層書架上，第四和第五本書放在最后一層書架上。

每一層所擺放的書的最大高度就是這一層書架的層高，書架整體的高度為各層高之和。

以這種方式布置書架，返回書架整體可能的最小高度。

示例：

image

輸入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
輸出：6
解釋：
3 層書架的高度和為 1 + 3 + 2 = 6 。
第 2 本書不必放在第一層書架上。

題目解析

一個(gè)典型的動(dòng)態(tài)規(guī)劃，dp[i]表示當(dāng)?shù)趇本數(shù)為最后一個(gè)本數(shù)的最小高度，狀態(tài)轉(zhuǎn)移方程為dp[i] = min(dp[i], dp[j-1] + h), 其中j表示最后一層所有書的索引，其中sum(book[j][0]) <= shelf_width。h則表示這些書中的最大高度。

C++代碼

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        int n = books.size();
        vector<int> dp(n+1,1000*1000);
        dp[0] = 0;
        for(int i = 1; i <=n; i++) {
            int j = i;
            int tmpWidth = 0;
            int h = 0;
            while(j) {
                tmpWidth += books[j - 1][0];                
                if(tmpWidth > shelf_width) break;
                h = max(h, books[j - 1][1]);
                dp[i] = min(dp[i], dp[j-1] + h);
                j--;
            }
        }
        return dp[n];
    }
};