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]代表以当前这本书为本层书架最后一本书的时候，目前我们建的书架的最小高度。
当我们计算到书本i的时候，假设这本书是当前level最后一本书，那么我们可以尝试把之前的书本加入到本层书架来，只要这些书本的宽度不超过规定的宽度，在这个过程中。我们会找到以当前这本书为本层书架最后一本书为前提条件的时候，我们目前建立的书架最小的高度。然后把它更新到dp数组中。最后一个值就是我们的答案。
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();
}
};
