※ 引述《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;
}
};