Re: [閒聊] 每日leetcode已回收
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-- {
width := books[j][0]
height := books[j][1]
if width+CurWidth > maxShelfWidth {
break
}
CurWidth += width
CurHeight = max(CurHeight, height)
Totalheight := CurHeight + dp[j]
dp[i] = min(dp[i], Totalheight)
}
}
return dp[n]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722428436.A.6AF.html
推
07/31 20:31,
1年前
, 1F
07/31 20:31, 1F
→
07/31 20:48,
1年前
, 2F
07/31 20:48, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 603 之 1548 篇)：