Filling Bookcase Shelves 填充書架
問題描述：
給定一個數(shù)組 books ，其中 b o o k s [ i ] = [ t h i c k n e s s i , h e i g h t i ] books[i] = [thicknessi, heighti] books[i]=[thicknessi,heighti] 表示第 i 本書的厚度和高度。你也會得到一個整數(shù) shelfWidth 。
按順序 將這些書擺放到總寬度為 shelfWidth 的書架上。
先選幾本書放在書架上（它們的厚度之和小于等于書架的寬度 shelfWidth ），然后再建一層書架。重復這個過程，直到把所有的書都放在書架上。
需要注意的是，在上述過程的每個步驟中，擺放書的順序與給定圖書數(shù)組 books 順序相同。
例如，如果這里有 5 本書，那么可能的一種擺放情況是：第一和第二本書放在第一層書架上，第三本書放在第二層書架上，第四和第五本書放在最后一層書架上。
每一層所擺放的書的最大高度就是這一層書架的層高，書架整體的高度為各層高之和。
以這種方式布置書架，返回書架整體可能的最小高度。
books.length , thickness[i],height[i] ,shelfWidth 范圍[1,1000]
分析
問題本身是一個具象的書架問題，書本以數(shù)組的結(jié)構(gòu)給出，而且限制必須是連續(xù)的。
也就是說要對數(shù)組劃分組，每一組的要求是厚度累加不超過書架的寬度 s h e l f w i d t h shelfwidth shelfwidth，同時該層書架的高度是由這一組書中最高的高度決定的。
因為有順序的限制，問題的難度就小了。
要求計算書架的最小高度。
如果要書架高度最小，最理想的情況，就是一層， h i g h = m a x b o o k high=maxbook high=maxbook。
但是由于width的限制，所以每一層的 b o o k book book數(shù)量也是由 w i d t h width width限制。
從0開始計算，如果 0 → i ? 1 0\rightarrow i-1 0→i?1已經(jīng)放好，此時為 x x x層， x x x層的高度為 h 1 h1 h1，那么 b o o k [ i ] book[i] book[i]就是新一層的第一本，此刻書架高度就是 h 1 + b o o k [ i ] . h i g h h1+book[i].high h1+book[i].high。
定義一個 f [ i ] , f [ i ] 表示 0 → i 本書放完時，書架的最小高度 f[i],f[i]表示 0\rightarrow i本書放完時，書架的最小高度 f[i],f[i]表示0→i本書放完時，書架的最小高度。
b o o k [ i ] book[i] book[i]為最后一層的第1本， f [ i ] = f [ i ? 1 ] + b o o k [ i ] . h i g h f[i]= f[i-1]+book[i].high f[i]=f[i?1]+book[i].high,
b
o
o
k
[
i
]
book[i]
book[i]為最后一層的第2本，
f
[
i
]
=
f
[
i
?
2
]
+
m
a
x
(
b
o
o
k
[
i
]
.
h
i
g
h
,
b
o
o
k
[
i
?
1
]
.
h
i
g
h
)
f[i]= f[i-2]+ max(book[i].high,book[i-1].high)
f[i]=f[i?2]+max(book[i].high,book[i?1].high),可以推出
f
[
i
]
=
f
[
j
?
1
]
+
m
a
x
(
j
?
i
)
,
∑
j
<
=
p
<
=
i
b
o
o
k
[
p
]
<
w
i
d
t
h
f[i] = f[j-1]+max(j~i), \sum_{j<=p<=i}{book[p]}<width
f[i]=f[j?1]+max(j?i),j<=p<=i∑?book[p]<width
代碼
class Solution {
public int minHeightShelves(int[][] books, int shelfWidth) {
int n = books.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, 1000000);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
int maxHeight = 0, curWidth = 0;
for (int j = i; j >= 0; --j) {
curWidth += books[j][0];
if (curWidth > shelfWidth) {
break;
}
maxHeight = Math.max(maxHeight, books[j][1]);
dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
}
}
return dp[n];
}
}
時間復雜度 O( N 2 N^{2} N2) 空間復雜度： O ( N ) O(N) O(N)
Tag文章來源：http://www.zghlxwxcb.cn/news/detail-473426.html
Array Dynamic Programming文章來源地址http://www.zghlxwxcb.cn/news/detail-473426.html
到了這里，關(guān)于【算法】Filling Bookcase Shelves 填充書架的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
