1105. Filling Bookcase Shelves
给你一堆书
每个书都有自己的高度和宽度 books[i]=[thickness_i,height_i]
书架每一层最大宽度为shelfWidth
高度为该该层书架最高的那本书
请问可以放进所有书的书架最低高度为?
思路:
dp问题
我不会，对阿
偷看了一下
就用一个dp array
其中dp[i]代表能装进0~i-1本书的书架最低的高度
然后每次遇到一本书books[i]
就往回找，在shelfWidth的范围内，看最低的高度为和
maxHeight为这层最高的书的高度
dp[i]=min[dp[i],dp[j]+maxHeight]
最后就可以得到答案了
golang code :
func minHeightShelves(books [][]int, maxShelfWidth int) int {
n := len(books)
dp := make([]int, n+1)
for i := range dp[:] {
dp[i] = math.MaxInt32
}
dp[0] = 0
for i := 1; i < n+1; i++ {
CurWidth := 0
CurHeight := 0
for j := i - 1; j >= 0; j