※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 1105. Filling Bookcase Shelves
: 给你一堆书
一开始看
还是先sort好了 我家柜子都这样摆
欸不对 顺序不能动
啊不然递回全部塞塞看
多做这么多次好白痴喔看一下constrain
才1000ㄛ开个dp计好了
>.0~*
来改成iterative 试试 好酷 你版人都好厉害
class Solution {
public:
vector<int> minH = vector<int>(1000, -1);
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
//windowsize = shelfWidth
int n = books.size();
minH[n-1] = books[n-1][1];
return count_minH(books, shelfWidth, 0);
}
int count_minH(vector<vector<int>>& books, int& shW, int idx){
//<[0]thick, [1]height>
if(idx >= books.size()) return 0;
if(minH[idx] != -1) return minH[idx];
int size = 0, maxH = 0, res = INT_MAX;
for(int i = idx; i < books.size() ; i++){
size += books[i][0];
if(size > shW) break;
maxH = max(maxH, books[i][1]);
res = min(res, maxH + count_minH(books, shW, i+1));
cout << res << '\n';
}
minH[idx] = res;
return res;
}
};