資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中填充書架
假設我們有一系列書籍 - 這裡第 i 本書的厚度為 books[i][0]，高度為 books[i][1]。如果我們想按順序將這些書放在總寬度為 shelf_width 的書架上。如果我們選擇一些書放在這個書架上（使得它們的厚度之和 <= shelf_width），然後構建書櫃的另一層，書櫃的總高度增加了我們可以放下的書籍的最大高度。我們將重複此過程，直到沒有更多書籍可以放置。我們必須記住，在上述過程的每個步驟中，我們放置書籍的順序與給定的書籍序列的順序相同。我們必須找到以這種方式放置書架後書架的總高度的最小可能高度。因此，如果輸入類似於 - [[1,1], [2,3], [2,3], [1,1], [1,1], [1,1], [1,2]]，並且 self_width = 4，
則輸出將為 6，因為 3 個書架的高度之和為 1 + 3 + 2 = 6。請注意，第 2 本書不必放在第一個書架上。
為了解決這個問題，我們將遵循以下步驟 -
- 建立一個大小與 books 相同的陣列 dp，並使用無限填充它
- dp[0] := books[0,1]
- 對於 i 從 1 到 books 的長度 - 1
- curr_height := 0
- temp := self_width
- j := i
- 當 j >= 0 且 temp – books[j, 0] >= 0 時，執行
- curr_height := books[j, 1] 和 curr_height 的最大值
- dp[i] := dp[i]、curr_height + (如果 j – 1 >= 0 則為 dp[j - 1]，否則為 0) 的最小值
- temp := temp – books[j, 0]
- 將 j 減 1
- 返回 dp 的最後一個元素
讓我們看看以下實現以更好地理解 -
示例
class Solution(object):
def minHeightShelves(self, books, shelf_width):
"""
:type books: List[List[int]]
:type shelf_width: int
:rtype: int
"""
dp = [float('inf') for i in range(len(books))]
dp[0] = books[0][1]
for i in range(1,len(books)):
current_height = 0
temp = shelf_width
j = i
while j>=0 and temp-books[j][0]>=0:
current_height = max(books[j][1],current_height)
dp[i] = min(dp[i],current_height +( dp[j-1] if j-1 >=0 else 0))
temp-=books[j][0]
j-=1
#print(dp)
return dp[-1]輸入
[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]] 4
輸出
6
更新於: 2020-03-05
474 次檢視
廣告