主題
題目連結(jié)：
題目意譯：
你被給定一個陣列 books，其中 books[i] = [thicknessi, heighti] 代表著第 i 本書的寬度和高度。同時你也被給定一個整數(shù) shelfWidth。
我們想要將這些書籍按照順序放到若干層的書架上，而每層書架的寬度 shelfWidth。
我們會在每一層書架選定並放入若干書籍使得這些書的寬度總和不超過 shelfWidth，並且整個書櫃的高度將增高等價於放置於此層書架中的書籍最大高度值。重複此步驟直到?jīng)]有書本可以繼續(xù)放為止。
注意到上述過程中的每一步放的書籍之順序必須與給定的書籍順序相同。
例如說，如果我們有一個 5 本書的有序列表。則我們可以在第一層放入第一本和第二本、第三本放到第二層，並將第四本和第五本書放到第三層中。
回傳放完書籍後，整個書櫃最小可能總高度。
限制：
1 ≦ books.length ≦ 1000
1 ≦ thicknessi ≦ shelfWidth ≦ 1000
1 ≦ heighti ≦ 1000
範(fàn)例測資：
範(fàn)例 1：
輸入： books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
輸出： 6
解釋：
3 層書架高度總和為 1 + 2 + 3 = 6。
注意到 2 號書本不一定要在第一層。
範(fàn)例 2：
輸入： books = [[1,3],[2,4],[3,2]], shelfWidth = 6
輸出： 4
解題思維：
（令 n = books.length）
由於每一本書要按照順序放，因此可以看到最後一層的書（這邊的編號是從 0 開始數(shù)）會是編號 n - 1 、 n - 2 、 …… 的書。
假設(shè)我們「只」知道最後一層要放最後 k 本書，因此最後一層會是編號 n - 1 、 n - 2 、 …… 、 n - k 的書。而一旦我們將這些去掉之後，倒數(shù)第二層將會變成「新的」最後一層，而編號 n - k - 1 的書將會變成新的「n」。
而實際上我們不知道 k 值是多少，所以我們可以選擇窮舉可能的 k 值（當(dāng)然，記得要滿足挑出來的 k 本書總寬度不超過 shelfWidth），即 k = 1 、 2 、 …… 並將問題從求 n 本書變成求 n - k 本書。
因此可以看到本題可以用動態(tài)規(guī)劃（Dynamic Programming）的精神解開。
定義一個陣列 D，其中 D[i] 代表著前 i 本書可以形成的書櫃最小高度為何。可以看到其遞迴式為：
D[0] = 0、
（上式為遞迴停止條件）
D[i] = min(max(books[i][1], books[i - 1][1], ……, books[j][1]) + D[j - 1])，對於所有滿足 1 ≦ j ≦ i 且 books[i - 1][0] + books[i - 2][0] + …… + books[j][0] ≦ shelfWidth 的 j 值。
而所求即為 D[n]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
