Description:

image.png

Example:

image.png

Link:

https://leetcode.com/problems/filling-bookcase-shelves/

解題方法：

DP:
dp[i] represents the minimum height of total shelves we build that ended by books[i].
For a given book with index i, assume this book is the last book in current level, then we can try to add other books with index < i into our current level, unless the total width of current level is bigger than the limit shelf_width. During this process, we will find out the minimum height of total shelves we've build, which is the dp[i] we are trying to figure out for current book.

dp[i]代表以當(dāng)前這本書為本層書架最后一本書的時(shí)候，目前我們建的書架的最小高度。
當(dāng)我們計(jì)算到書本i的時(shí)候，假設(shè)這本書是當(dāng)前l(fā)evel最后一本書，那么我們可以嘗試把之前的書本加入到本層書架來，只要這些書本的寬度不超過規(guī)定的寬度，在這個(gè)過程中。我們會(huì)找到以當(dāng)前這本書為本層書架最后一本書為前提條件的時(shí)候，我們目前建立的書架最小的高度。然后把它更新到dp數(shù)組中。最后一個(gè)值就是我們的答案。

Time Complexity：

O（n^2)

完整代碼：

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        vector<int> dp;
        int size = books.size();
        if(!size)
            return 0;
        dp.push_back(books[0][1]);
        for(int i = 1; i < size; i++) {
            int currWidth = books[i][0];
            int maxHeight = books[i][1];
            int minDp = maxHeight + dp.back();
            for(int j = dp.size() - 1; j >= 0; j--) {
                currWidth += books[j][0];
                if(currWidth > shelf_width)
                    break;
                maxHeight = max(maxHeight, books[j][1]);
                if(j == 0)
                    minDp = min(maxHeight, minDp);
                else
                    minDp = min(maxHeight + dp[j - 1], minDp);
            }
            dp.push_back(minDp);
        }
        return dp.back();
    }
};