LeetCode 1105. 填充书架

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 1105. 填充书架

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i] 表示放置前 i 本书的最小高度。

枚举最后一层放置的书，从 i 向前扩展并维护层内最大高度。

当层宽超过限制时停止扩展。

复杂度分析：

时间复杂度：O(n^2)，其中 n 为书本数量。

空间复杂度：O(n)。

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE / 2;
            int width = 0;
            int height = 0;
            for (int j = i; j >= 1; j--) {
                width += books[j - 1][0];
                if (width > shelfWidth) {
                    break;
                }
                height = Math.max(height, books[j - 1][1]);
                dp[i] = Math.min(dp[i], dp[j - 1] + height);
            }
        }
        return dp[n];
    }
}

func minHeightShelves(books [][]int, shelfWidth int) int {
    n := len(books)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = 1 << 30
        width := 0
        height := 0
        for j := i; j >= 1; j-- {
            width += books[j-1][0]
            if width > shelfWidth {
                break
            }
            if books[j-1][1] > height {
                height = books[j-1][1]
            }
            if dp[j-1]+height < dp[i] {
                dp[i] = dp[j-1] + height
            }
        }
    }
    return dp[n]
}

相似题目

题目	难度	考察点
198. 打家劫舍	中等	DP
1043. 分隔数组以得到最大和	中等	DP
221. 最大正方形	中等	DP
1105. 填充书架	中等	DP
300. 最长递增子序列	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/35776576