Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
推 sustainer123: 大師
→ DJYOMIYAHINA: 我有什麼用