Re: [閒聊] 每日leetcode已回收
1105. Filling Bookcase Shelves
## 思路
DP[i] = books[i:] 的最小高度總和
= min(i..j的最大高度 + DP[j+1]) <-- i~j本書的寬度和不大於shelfWidth
## Complexity
Time: O(N min(N,W))
Space: O(N)
## Code
```python
class Solution:
def minHeightShelves(self, books: List[List[int]], shelfWidth: int) ->
int:
n = len(books)
ans = 0
@cache
def dp(i):
if i == n:
return 0
res = float('inf')
curr_width = curr_height = 0
for j in range(i, n):
curr_height = max(curr_height, books[j][1])
curr_width += books[j][0]
if curr_width > shelfWidth:
break
res = min(res, curr_height + dp(j+1))
return res
return dp(0)
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.24 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722387467.A.72A.html
※ 編輯: dont (185.213.82.24 臺灣), 07/31/2024 09:00:45
推
07/31 09:10,
1年前
, 1F
07/31 09:10, 1F
補個forloop版本
```python
class Solution:
def minHeightShelves(self, books: List[List[int]], shelfWidth: int) ->
int:
n = len(books)
ans = 0
dp = [float('inf')] * (1+n)
dp[n] = 0
for i in range(n-1, -1, -1):
curr_width = curr_height = 0
for j in range(i, n):
curr_height = max(curr_height, books[j][1])
curr_width += books[j][0]
if curr_width > shelfWidth:
break
dp[i] = min(dp[i], curr_height + dp[j+1])
return dp[0]
```
※ 編輯: dont (185.213.82.83 臺灣), 07/31/2024 09:16:40
討論串 (同標題文章)
完整討論串 (本文為第 599 之 1553 篇)：