Leetcode Problem 1105. Filling Bookcase Shelves

1105. Filling Bookcase Shelves

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a dp array of size books.length + 1 with dp[0] = 0.
  2. Iterate through the books from 1 to books.length.
  3. For each book i, initialize width as the thickness of the current book and height as the height of the current book.
  4. Set dp[i] to dp[i-1] + height (placing the book on a new shelf).
  5. Iterate backwards from book i-1 to 1, and for each book j, check if the sum of widths from j to i is less than or equal to shelfWidth.
  6. Update the height to the maximum height of the books from j to i.
  7. Update dp[i] to the minimum of its current value and dp[j-1] + height (placing books j to i on the same shelf).
  8. After filling the dp array, return dp[books.length] as the answer.
UML Thumbnail

DFS with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...