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