填充书架 图解题解

书按顺序上架，怎么分层才能让书架最矮

给一排书 books，每本是 [厚度、高度]，书架宽度 shelfWidth。书按给定顺序摆、不能打乱；同层厚度之和不超过 shelfWidth，放不下就另起一层。层高是这层最高那本的高度，总高是各层相加，求最小总高。演示 books=[[1,3],[2,1],[2,3],[1,4],[2,2]]、shelfWidth=4，答案 9。

为什么不能把每种分层方式都试一遍

每两本相邻的书之间都能选「断开」或「连一层」，n 本就有 2ⁿ⁻¹ 种分法，逐一算指数级炸开，且大量分法共享前缀被反复重算。既然「前 i 本怎么摆最矮」能独立回答，算一次存下来复用，就是动态规划（把『前 i 本书怎么摆最矮』算一次存下、后面直接取）。

状态定义：f[i] 存什么，f[0] 为什么是 0

定义 f[i] 为「前 i 本摆完能做到的最小总高」（把答案记进第 i 格，要用直接取）。下标 i 数的是书的本数、不是位置。f[0]=0：一本没摆、高度为 0，给后面递推（拿前面算好的推出后面的）当地基。答案是 f[n]。

转移（从前面算好的格子推出这一格）：枚举最后一层从哪本起

算 f[i] 只盯最后一层装哪几本连续的书。设它从第 j 本到第 i 本，前 j-1 本取最优 f[j-1]，这层层高是第 j 到 i 本里最高那本，于是 f[i] = f[j-1] + 这层最大高度。先给保底 f[i] = f[i-1] + 它的高度。

再让最后一层从第 i 本往左扩，累加新并那本的厚度。一旦超过 shelfWidth 就直接停（厚度只增不减、再往左更宽，一超即停）。没超就用 max 把层高更新成段内最高的一本，拿 f[j-1] + 层高刷新 f[i] 取更小。

拿这 5 本书把 f 表从左填到右

厚度 1、2、2、1、2，高度 3、1、3、4、2，shelfWidth=4，f[0]=0。

f[1]=f[0]+3=3。f[2]：保底 4；并第 1、2 本厚 3、层高 3，得 f[0]+3=3，f[2]=3。f[3]：保底 6；并第 2、3 本厚 4、层高 3 得 6 不更小，再并第 1 本厚 5 超宽停，f[3]=6。

f[4]：保底 10；并第 3、4 本厚 3、层高 max(4,3)=4，得 f[2]+4=7，f[4]=7。f[5]：保底 9；并第 4、5 本厚 3、层高 max(2,4)=4 得 10 不更小，f[5]=9 即答案，分层 [书1,书2]、[书3,书4]、[书5]。

漏了取 max、层高用成刚并进那本，总高为什么会算矮

外层 i 走 n 本、内层最坏从第 i 本往左扫到第 1 本，每格 O(n)，合起来时间 O(n²)（大 O 记号，描述规模变大时操作数大概怎么涨）；书厚时内层很快 break。空间只额外开长度 n+1 的数组 f，是 O(n)。

边界：全部塞一层时层高是最高那本；只有一本时答案是它的高度；厚度恰好等于 shelfWidth 也算放得下，判断用「超过才停」而非「大于等于就停」；超宽别写成「跳过往左」，该 break 不 break 会算进非法分层。

漏了 max、用刚并那本的高度，就把某层算矮。

Python

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]

C++

#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];
    }
};

Java

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];
    }
}