Skip to content

1105. Filling Bookcase Shelves 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
    // dp[i] := the minimum height to place the first i books
    vector<int> dp(books.size() + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < books.size(); ++i) {
      int sumThickness = 0;
      int maxHeight = 0;
      // Place books[j..i] on a new shelf.
      for (int j = i; j >= 0; --j) {
        const int thickness = books[j][0];
        const int height = books[j][1];
        sumThickness += thickness;
        if (sumThickness > shelfWidth)
          break;
        maxHeight = max(maxHeight, height);
        dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight);
      }
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int minHeightShelves(int[][] books, int shelfWidth) {
    final int n = books.length;
    // dp[i] := the minimum height to place the first i books
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 0; i < books.length; ++i) {
      int sumThickness = 0;
      int maxHeight = 0;
      // Place books[j..i] on a new shelf.
      for (int j = i; j >= 0; --j) {
        final int thickness = books[j][0];
        final int height = books[j][1];
        sumThickness += thickness;
        if (sumThickness > shelfWidth)
          break;
        maxHeight = Math.max(maxHeight, height);
        dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
      }
    }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def minHeightShelves(self, books: list[list[int]], shelfWidth: int) -> int:
    # dp[i] := the minimum height to place the first i books
    dp = [0] + [math.inf] * len(books)

    for i in range(len(books)):
      sumThickness = 0
      maxHeight = 0
      # Place books[j..i] on a new shelf.
      for j in range(i, -1, -1):
        thickness, height = books[j]
        sumThickness += thickness
        if sumThickness > shelfWidth:
          break
        maxHeight = max(maxHeight, height)
        dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)

    return dp[-1]