일련의 책이 있다고 가정합니다. 여기서 i 번째 책에는 두께 책[i][0]과 높이 책[i][1]이 있습니다. 전체 너비가 shelf_width인 책장에 이 책을 순서대로 배치하려는 경우. 이 선반에 놓을 책 중 일부를 선택하면(두께의 합이 <=shelf_width가 되도록), 책장의 총 높이가 최대 높이만큼 증가한 책장의 다른 수준의 선반을 만듭니다. 우리가 내려놓을 수 있는 책. 더 이상 배치할 책이 없을 때까지 이 과정을 반복합니다. 위 과정의 각 단계에서 우리가 놓는 책의 순서는 주어진 책의 순서와 같은 순서라는 것을 명심해야 합니다. 이러한 방식으로 선반을 배치한 후 전체 책장이 될 수 있는 최소 가능한 높이를 찾아야 합니다. 따라서 입력이 − [[1,1], [2,3], [2,3], [1,1], [1,1], [1,1], [1,2]]와 같은 경우 , 그리고 self_width =4,
3개의 선반 높이의 합이 1 + 3 + 2 =6이므로 출력은 6이 됩니다. 책 번호 2가 첫 번째 선반에 있을 필요는 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 책과 같은 크기의 배열 dp를 하나 만들고 무한대로 채웁니다.
- dp[0] :=책[0,1]
- 범위 1에서 책의 길이까지의 경우 – 1
- curr_height :=0
- temp :=self_width
- j :=나
- while j>=0 및 temp – books[j, 0]>=0, do
- curr_height :=최대 책[j, 1], curr_height
- dp[i] :=dp[i]의 최소값, curr_height + (dp[j - 1] if j – 1>=0, 그렇지 않으면 0)
- temp :=temp – 책[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