forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathfilling-bookcase-shelves.py
More file actions
49 lines (39 loc) · 1.4 KB
/
filling-bookcase-shelves.py
File metadata and controls
49 lines (39 loc) · 1.4 KB
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
dp[i] := min height when storing books 0~i
for each j try to add a new line at i, see the min height.
Time: O(N^2)
Space: O(N)
"""
class Solution(object):
def minHeightShelves(self, books, shelf_width):
N = len(books)
dp = [float('inf')]*N
for j in xrange(N):
w = 0
h = 0
for i in xrange(j, -1, -1):
w+=books[i][0]
if w>shelf_width: break
h = max(h, books[i][1])
if i==0:
dp[j] = min(dp[j], h)
else:
dp[j] = min(dp[j], dp[i-1]+h)
return dp[-1]
"""
dp[i] := smallest height that the last book on book shelve is books[i]
dp[i] = min { dp[j]+max(books[j+1:i]) where sumWidth(books[j+1:i])<=W, j = 0~i-1}
"""
class Solution(object):
def minHeightShelves(self, books, W):
dp = [float('inf')]*len(books)
dp[0] = books[0][1]
for i in xrange(1, len(books)):
topLevelWidth = 0
topLevelMaxHeight = 0
for j in xrange(i, -1, -1):
topLevelWidth += books[j][0]
topLevelMaxHeight = max(topLevelMaxHeight, books[j][1])
if topLevelWidth>W: break
dp[i] = min(dp[i], (dp[j-1] if j-1>=0 else 0) + topLevelMaxHeight)
return dp[-1]