LeetCode Entry
1105. Filling Bookcase Shelves
Min total height to split [[w,h]] array by shelfWidth programming
1105. Filling Bookcase Shelves medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/687
Problem TLDR
Min total height to split [[w,h]] array by shelfWidth #medium #dynamic_programming
Intuition
Let’s do a Depth-First search by the current book position: start forming a shelf by adding books while they are fit into shelfWidth and after each book try to stop and go to the next level dfs. Result is only depends on the starting position, so can be cached.
The bottom up Dynamic Programming algorithm can be thought like this: walk over the books and consider each i the end of the array; now choose optimal split before in [..i] books but not wider than shelf_width. Previous dp[j] are known, so we can compute dp[i] = min[h_max + dp[j]].
Approach
Let’s write DFS in Kotlin and bottom-up DP in Rust. Can you make it shorter?
Complexity
-
Time complexity: \(O(nm)\), where m is an average books count on the shelf; O(n^2) for solution without the
break -
Space complexity: \(O(n)\)
Code
fun minHeightShelves(books: Array<IntArray>, shelfWidth: Int): Int {
val dp = mutableMapOf<Int, Int>()
fun dfs(j: Int): Int = if (j < books.size) dp.getOrPut(j) {
var w = 0; var h = 0
(j..<books.size).minOf { i ->
w += books[i][0]; h = max(h, books[i][1])
if (w > shelfWidth) Int.MAX_VALUE else h + dfs(i + 1)
}
} else 0
return dfs(0)
}
pub fn min_height_shelves(books: Vec<Vec<i32>>, shelf_width: i32) -> i32 {
let mut dp = vec![i32::MAX / 2; books.len()];
for i in 0..dp.len() {
let mut w = 0; let mut h = 0;
for j in (0..=i).rev() {
w += books[j][0];
if w > shelf_width { break }
h = h.max(books[j][1]);
dp[i] = dp[i].min(h + if j > 0 { dp[j - 1] } else { 0 })
}
}; dp[dp.len() - 1]
}