สมมติว่าเรามีหนังสือเป็นลำดับ - ที่นี่หนังสือเล่มที่ i มีหนังสือความหนา[i][0] และความสูง[i][1] หากเราต้องการจัดวางหนังสือเหล่านี้บนชั้นวางหนังสือที่มีความกว้างทั้งหมด หากเราเลือกหนังสือบางเล่มที่จะวางบนชั้นวางนี้ (เช่น ผลรวมของความหนาคือ <=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 ไม่จำเป็นต้องอยู่บนชั้นแรก
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างหนึ่งอาร์เรย์ dp ที่มีขนาดเท่ากับหนังสือ และเติมค่านี้โดยใช้อนันต์
- dp[0] :=หนังสือ[0,1]
- สำหรับฉันอยู่ในช่วง 1 ถึงความยาวของหนังสือ – 1
- curr_height :=0
- อุณหภูมิ :=self_width
- j :=ฉัน
- ในขณะที่ j>=0 และ temp – books[j, 0]>=0, do
- curr_height :=สูงสุดของหนังสือ[j, 1], curr_height
- dp[i] :=นาทีของ dp[i], curr_height + (dp[j - 1] ถ้า j – 1>=0, มิฉะนั้น 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
