填充书架 图解题解

这道题到底在问什么

输入

books=[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth=4

输出

6

输入

本节演示 books=[[1,3],[2,1],[2,3],[1,4],[2,2]], shelfWidth=4

输出

9

先想最直接的笨办法

套路就一句:枚举「最后一层装哪几本连续的书」。最后一层选定后,前面那些书就是规模更小的同一个问题 f[j-1],加上这一层的层高即可。下面把 f 表一格一格填出来。（动画第 3 步）

最优解：一步一步想明白

1. 3套路就一句:枚举「最后一层装哪几本连续的书」。最后一层选定后,前面那些书就是规模更小的同一个问题 f[j-1],加上这一层的层高即可。下面把 f 表一格一格填出来。
2. 4先把数据摆出来。上面 5 个格子是 5 本书的高度,分别是 3、1、3、4、2;它们的厚度写在下面那行,依次是 1、2、2、1、2;书架宽度是 4。记住每本书是 [厚度, 高度] 一对值,厚度决定能不能挤进同一层,高度决定那层多高。
3. 5搭一张表,只有一行,列从左到右是 f[0] 到 f[5]。最左边 f[0] 先填 0:一本书都没摆,高度自然是 0。它是后面所有递推的地基。我们从 f[1] 往右一格一格填。
4. 6算 f[1]。先给一个保底方案:让第 1 本书(厚 1、高 3)自己单独占最后一层。那总高就是「前 0 本的最优」f[0]=0 再加上它自己的高 3,等于 3。先把这个值记进 f[1],下面看能不能把它跟前面的书拼一层、拼出更矮的。
5. 7所有放法都比过了,f[1] 最终是 3,意思是把前 1 本书摆完,书架最矮能做到 3。这格定死,继续往右算下一格。
6. 8算 f[2]。先给一个保底方案:让第 2 本书(厚 2、高 1)自己单独占最后一层。那总高就是「前 1 本的最优」f[1]=3 再加上它自己的高 1,等于 4。先把这个值记进 f[2],下面看能不能把它跟前面的书拼一层、拼出更矮的。
7. 9试着把第 1 到第 2 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 3。那么总高 = 前 0 本的最优 f[0]=0 加上这层高 3,等于 3。它比刚才记的还小,把 f[2] 刷新成 3。
8. 10所有放法都比过了,f[2] 最终是 3,意思是把前 2 本书摆完,书架最矮能做到 3。这格定死,继续往右算下一格。
9. 11算 f[3]。先给一个保底方案:让第 3 本书(厚 2、高 3)自己单独占最后一层。那总高就是「前 2 本的最优」f[2]=3 再加上它自己的高 3,等于 6。先把这个值记进 f[3],下面看能不能把它跟前面的书拼一层、拼出更矮的。
10. 12试着把第 2 到第 3 本书放在同一层。它们厚度之和是 4,没超过 4,能放;这一层的高度取这几本里最高的,是 3。那么总高 = 前 1 本的最优 f[1]=3 加上这层高 3,等于 6。它没有更小,f[3] 还是 6,不动。
11. 13想把更前面的第 1 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[3] 的扩展到此为止。
12. 14所有放法都比过了,f[3] 最终是 6,意思是把前 3 本书摆完,书架最矮能做到 6。这格定死,继续往右算下一格。
13. 15算 f[4]。先给一个保底方案:让第 4 本书(厚 1、高 4)自己单独占最后一层。那总高就是「前 3 本的最优」f[3]=6 再加上它自己的高 4,等于 10。先把这个值记进 f[4],下面看能不能把它跟前面的书拼一层、拼出更矮的。
14. 16试着把第 3 到第 4 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 4。那么总高 = 前 2 本的最优 f[2]=3 加上这层高 4,等于 7。它比刚才记的还小,把 f[4] 刷新成 7。
15. 17想把更前面的第 2 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[4] 的扩展到此为止。
16. 18所有放法都比过了,f[4] 最终是 7,意思是把前 4 本书摆完,书架最矮能做到 7。这格定死,继续往右算下一格。
17. 19算 f[5]。先给一个保底方案:让第 5 本书(厚 2、高 2)自己单独占最后一层。那总高就是「前 4 本的最优」f[4]=7 再加上它自己的高 2,等于 9。先把这个值记进 f[5],下面看能不能把它跟前面的书拼一层、拼出更矮的。
18. 20试着把第 4 到第 5 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 4。那么总高 = 前 3 本的最优 f[3]=6 加上这层高 4,等于 10。它没有更小,f[5] 还是 9,不动。
19. 21想把更前面的第 3 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[5] 的扩展到此为止。
20. 22所有放法都比过了,f[5] 最终是 9,意思是把前 5 本书摆完,书架最矮能做到 9。这格定死,表已经填完,下一步读出答案。
21. 23整张表填完了。最右边 f[5] 就是把 5 本书全部摆完的最小总高度,等于 9,这正是题目要的答案。回头看一眼这张表是怎么一步步长出来的:每一格都靠它左边某一格加上最后一层的层高得来。
22. 24顺着每格当初选的方案倒推一遍分层:f[5]=9 是让书5 单独成一层、接在 f[4] 后面;f[4]=7 是书3、书4 同一层(高 4)、接在 f[2] 后面;f[2]=3 是书1、书2 同一层(高 3)、接在 f[0] 后面。于是三层分别是 [书1,书2]、[书3,书4]、[书5]。
23. 25把最优分层标回原始的书上:绿色的书1、书2 是第一层,厚度 1+2=3 没超 4,层高取两本里高的 3;蓝色的书3、书4 是第二层,厚 2+1=3,层高 4;红色的书5 自己一层,层高 2。三层加起来 3+4+2=9,和 DP 表算出的答案严丝合缝。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        f = [0] * (n + 1)
        for i, (w, h) in enumerate(books, 1):
            f[i] = f[i - 1] + h
            for j in range(i - 1, 0, -1):
                w += books[j - 1][0]
                if w > shelfWidth:
                    break
                h = max(h, books[j - 1][1])
                f[i] = min(f[i], f[j - 1] + h)
        return f[n]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        int n = books.size();
        int f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int w = books[i - 1][0], h = books[i - 1][1];
            f[i] = f[i - 1] + h;
            for (int j = i - 1; j > 0; --j) {
                w += books[j - 1][0];
                if (w > shelfWidth) {
                    break;
                }
                h = max(h, books[j - 1][1]);
                f[i] = min(f[i], f[j - 1] + h);
            }
        }
        return f[n];
    }
};

import java.util.*;
class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int w = books[i - 1][0], h = books[i - 1][1];
            f[i] = f[i - 1] + h;
            for (int j = i - 1; j > 0; --j) {
                w += books[j - 1][0];
                if (w > shelfWidth) {
                    break;
                }
                h = Math.max(h, books[j - 1][1]);
                f[i] = Math.min(f[i], f[j - 1] + h);
            }
        }
        return f[n];
    }
}

复杂度

面试官可能追问