Filling Bookcase Shelves: DP Đặt Sách Lên Kệ Tối Thiểu Chiều Cao

Đề bài: Cho list sách books[i] = [thickness, height] và độ rộng kệ shelf_width. Đặt sách theo thứ tự, mỗi kệ chứa sách liên tiếp, tổng thickness ≤ shelf_width. Chiều cao kệ = max height sách trên kệ đó. Tối thiểu tổng chiều cao bookshelf.

Ví dụ: books=[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width=4 → 6 (3 kệ: cao 1, 3, 2).

DP: dp[i] = min height cho books[0..i]

• Xét sách cuối cùng trên kệ cuối: thử lấy sách j..i (j từ i downto 0) miễn là thickness sum ≤ shelf_width.
• dp[i] = min(dp[j-1] + max_height(j..i)) với dp[-1] = 0.

Code Python

class Solution:
    def minHeightShelves(self, books: list[list[int]], shelf_width: int) -> int:
        n = len(books)
        dp = [float('inf')] * n
        
        for i in range(n):
            curr_width = 0
            curr_max_h = 0
            # Thử đặt sách j..i trên cùng một kệ
            for j in range(i, -1, -1):
                curr_width += books[j][0]
                if curr_width > shelf_width:
                    break
                curr_max_h = max(curr_max_h, books[j][1])
                prev = dp[j-1] if j > 0 else 0
                dp[i] = min(dp[i], prev + curr_max_h)
        
        return dp[-1]

# Test
ob = Solution()
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
print(ob.minHeightShelves(books, 4))  # 6

Phân tích

• Time: O(n²) worst case (nested loop). Tối ưu được với monotonic queue/deque nếu cần.
• Space: O(n).
• Inner loop break early khi width vượt shelf_width.

Kết luận

DP 1D kinh điển "partition array into segments with cost". Cost segment = max height. Thử mọi partition point j cho segment kết thúc tại i.