思路。最后一步只有三种：最后一束是 AAA（用了末三朵、且它们都是 0）、是 AB（用了末两朵、一 A 一 B，顺序不限）、或者末尾若干朵花根本不进任何花束。设 \(dp_i\) 为「只用前 \(i\) 朵花」能取得的最大价值，转移即为三者取最大：

方括号指示项不满足条件时取 \(-\infty\)（不合法）。关键在于「不扎」这一支保证了花可以剩下不用，且扎花的花必须相邻这一约束被「末 k 朵整体成束」编码进状态截断里。手算 \(f = [0,0,0,0,1]\)、\(p=10\)、\(q=6\)：\(dp_3 = 10\)（前三朵扎 AAA），\(dp_5 = \max(dp_4, dp_3 + q) = 16\)——前三朵扎 AAA、第四五朵（A、B 相邻）扎 AB，组合优于任何单一方案。

代码。

long long maxBouquetValue(const vector<int>& f, long long p, long long q) {
    int n = (int)f.size();
    vector<long long> dp(n + 1, 0);           // dp[i]：只用前 i 朵花的最大收益
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];                     // 第 i 朵不进任何花束
        if (i >= 3 && !f[i-1] && !f[i-2] && !f[i-3])
            dp[i] = max(dp[i], dp[i - 3] + p); // 末三朵 0,0,0 扎 AAA
        bool ab = (f[i-1] == 0 && f[i-2] == 1) || (f[i-1] == 1 && f[i-2] == 0);
        if (i >= 2 && ab)
            dp[i] = max(dp[i], dp[i - 2] + q); // 末两朵一 A 一 B 扎 AB
    }
    return dp[n];
}

复杂度。时间 \(O(n)\)，空间 \(O(n)\)（只需最近三个值，可滚动到 \(O(1)\)）。

边界。\(n \lt 2\) 时无法扎任何花束，返回 0；AB 是否区分顺序（A 在前还是 B 在前）建议向面试官确认，本实现两种都允许；p、q 可为 0 或负（亏本的花束不扎，dp 自然处理）。

面试怎么讲。先把「最后一步」说出来：最后一束花要么 AAA、要么 AB、要么末尾的花不用。这一句就是状态设计的全部；剩下的转移只是机械展开。追问「能不能输出扎法」时，在 dp 上记录每步的选择再回溯即可。

思路（建模是本题主角）。把第 \(i\) 列硬币的高度记为 \(h_i\)。水滴落下后，位置 \(i\) 处的水位不会超过「左侧最高硬币」与「右侧最高硬币」的较小者，因为超过就会从矮的一侧溢出。于是每列能稳定停留的水滴数为

总滴数即 \(\sum_i d_i\)。源题的「能存 2 滴」对应最小非平凡例子：高度 \([2, 0, 2]\)，中间列水位被两侧夹到 2，存 \(2 - 0 = 2\) 滴。\(L\) 与 \(R\) 各一次线性扫描即可预计算，这正是「前缀最值 + 后缀最值」的 DP。

代码。

long long totalDrops(const vector<int>& h) {  // h[i]：第 i 列硬币叠放的高度
    int n = (int)h.size();
    if (n == 0) return 0;
    vector<int> L(n), R(n);                    // 左/右两侧（含自身）最高的一列
    L[0] = h[0];
    for (int i = 1; i < n; ++i) L[i] = max(L[i-1], h[i]);
    R[n-1] = h[n-1];
    for (int i = n - 2; i >= 0; --i) R[i] = max(R[i+1], h[i]);
    long long total = 0;
    for (int i = 0; i < n; ++i)
        total += max(0, min(L[i], R[i]) - h[i]);   // 水位由两侧较矮者决定
    return total;
}

复杂度。时间 \(O(n)\)（三次线性扫描），空间 \(O(n)\)。

边界。单调不降或单调不增的高度数组存不了水（每列 \(\min(L_i,R_i) = h_i\)）；\(n \le 2\) 必然为 0；高度为 0 的「空列」也照样参与计算——它只是矮墙。这道题与源题库另一道「接雨水」（海拔图存水）是同一模型的不同皮，后者还有双指针 \(O(1)\) 空间解法，完整推导放在 033. 编程三：滑动窗口与前缀和的例题里。

面试怎么讲。先用「两侧较矮者决定水位」这句物理直觉立住公式，再说明为什么逐列求和是安全的（每列独立）。主动提接雨水变体与双指针优化，是漂亮的收尾。

思路。最后一步分类：从第 \(n-1\) 阶跨 1、从第 \(n-2\) 阶跨 2、从第 \(n-3\) 阶跨 3，互斥完备，得 tribonacci 递推（见知识讲解）。斐波那契正是「只允许跨 1 或 2 阶」的特例。复杂度问题的标准答案：朴素递归是指数级（斐波那契约 \(O(1.618^n)\)，因为递归树每层近似分裂成两个子问题）；递推填表是 \(O(n)\) 时间；只依赖前三个状态，空间滚动到 \(O(1)\)；若 n 极大还要取模并用矩阵快速幂 \(O(\log n)\)。

代码。

long long countWays(int n) {                  // f(n) = f(n-1) + f(n-2) + f(n-3)
    if (n <= 1) return 1;                     // 0 阶：站着不动，也是 1 种
    vector<long long> f(n + 1);
    f[0] = 1; f[1] = 1; f[2] = 2;             // 小情形直接给边界
    for (int i = 3; i <= n; ++i) f[i] = f[i-1] + f[i-2] + f[i-3];
    return f[n];
}

复杂度。\(O(n)\) 时间、\(O(n)\) 空间；滚动后 \(O(1)\) 空间。

边界。\(f_0 = 1\) 的口径（空走法算一种）要在写代码前说出口；\(f_2 = 2\)（1+1 或 2）。tribonacci 增长底约 1.839，\(n = 80\) 已接近 long long 上限，大 n 必须配取模。

面试怎么讲。「最后一步跨几阶」这句分类语言是全部内容；复杂度分析按「朴素递归 → 填表 → 滚动 → 矩阵幂」四档报出，展示你知道每档存在的理由，而不是背复杂度。

思路（DP 版）。设 \(dp_i\) 为到达下标 \(i\) 的最少步数，\(dp_0 = 0\)。正向转移：每个 \(i\) 把它能跳到的所有 \(j\) 松弛 \(dp_j = \min(dp_j, dp_i + 1)\)。源题的写法 \(\min(dp_i, dp_{i+j} + 1)\) 是从右往左倒推的同一件事（从终点往回看）。\(O(n^2)\)，正确但慢。

思路（贪心版）。把「一跳之内能到的位置」看成一层：维护当前层的右边界 end 与下一层最远可达 farthest，遍历到层边界时步数加一并进入下一层。每层只需一遍扫描，总 \(O(n)\)。本质是 BFS 的分层思想，因为每步代价相同，最先铺满的一定步数最少。

代码（贪心）。

int minJumps(const vector<int>& arr) {        // 贪心：按「一跳能到的层」逐层扩张
    int n = (int)arr.size();
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < n - 1; ++i) {
        farthest = max(farthest, i + arr[i]);
        if (i == end) {                        // 当前层的候选位置耗尽
            if (farthest <= i) return -1;      // 原地卡死，到不了终点
            ++jumps;                           // 跨入下一层
            end = farthest;
        }
    }
    return jumps;
}

手算 \([2, 3, 1, 1, 4]\)：i=0 时 farthest=2，触到层边界，jumps=1、end=2；i=1 时 farthest=max(2, 4)=4；i=2 触到 end，jumps=2、end=4；end 已越过终点，返回 2。

复杂度。DP 版 \(O(n^2)\) 时间、\(O(n)\) 空间；贪心版 \(O(n)\) 时间、\(O(1)\) 空间。

边界。首元素为 0 且 \(n \gt 1\) 时不可达（返回 −1 或按题意报错）；\(n = 1\) 起点即终点，0 步；\(arr_i\) 可能为 0，卡死检测（farthest 不再前进）必须要有。

面试怎么讲。先给 DP（对齐源题给的递推，说明等价），再主动升级到贪心并点破「同权边最短路 → BFS 分层」这个视角。能讲清贪心为什么对（每层是最少步数相同的位置集合）比背代码重要。

思路。「每段排序后拼接非降」当且仅当相邻两段之间，左段的最大值不超过右段的最小值（段内部排序解决，段之间靠这个条件）。于是位置 \(i\) 与 \(i+1\) 之间能切一刀，等价于 \(\max(a_1..a_i) \le \min(a_{i+1}..a_n)\)。从左到右维护前缀最大、从右到左维护后缀最小（即源题口径的「从右往左前缀 min」），一刀一刀数出来。对 \([3,2,1,4,6,5]\)：后缀最小数组为 \([1,1,1,4,5,5]\)，前缀最大扫描到下标 3 时为 4，检查 \(4 \le \min(6,5)=5\)，下标 3 与 4 之间可切；下标 2 与 3 之间 \(3 \le 4\) 也可切——自由切分下其实能切成 \([3,2,1]\)、\([4]\)、\([6,5]\) 三段。源题宣称答案是 2（\([3,2,1]\) 与 \([4,6,5]\)），对应的是「等长切段」或「每段长度至少为 2」的口径；这正好说明面试时先澄清切分约束的必要。

代码。

int maxParts(const vector<int>& a) {          // 自由切分口径下的最大段数
    int n = (int)a.size();
    vector<int> sufMin(n);                     // 从右往左维护的后缀最小值
    sufMin[n-1] = a[n-1];
    for (int i = n - 2; i >= 0; --i) sufMin[i] = min(a[i], sufMin[i+1]);
    int parts = 1, preMax = a[0];
    for (int i = 0; i + 1 < n; ++i) {          // 考察 i 与 i+1 之间能否切一刀
        preMax = max(preMax, a[i]);
        if (preMax <= sufMin[i+1]) ++parts;     // 左段全部 <= 右段全部
    }
    return parts;
}

复杂度。时间 \(O(n)\)，空间 \(O(n)\)。

边界。已排序数组每处皆可切，答案是 n；严格递减数组只能整段，答案 1；等长口径下需要检查每个 n 的因子，复杂度变为 \(O(n \cdot d(n))\)。

面试怎么讲。把「相邻段 max ≤ min」这个充要条件先证出来（两个方向各一句），代码就是查每个切位。主动指出源题答案 2 与自由切分答案 3 的口径差，展示澄清习惯。

思路。0/1 背包可达性：设 \(\mathrm{reach}(s)\) 为「和 s 能否被凑出」，逐件物品决策「不拿」或「拿」。第 \(x\) 件物品加入后，所有 \(s - x\) 可达的和使 \(s\) 可达：

实现上用一维布尔数组、容量从大到小枚举（倒序保证每件物品只用一次——正序会允许同一件被拿多次，变成完全背包）。目标 0 恒可达（空子集）。

代码。

bool canReach(const vector<int>& items, long long target) {  // 0/1 背包可达性
    if (target < 0) return false;
    vector<char> reach(target + 1, 0);
    reach[0] = 1;                              // 空子集的和为 0
    for (int x : items)
        for (long long s = target; s >= x; --s)   // 倒序：每件物品至多用一次
            if (reach[s - x]) reach[s] = 1;
    return reach[target];
}

复杂度。时间 \(O(n \cdot T)\)、空间 \(O(T)\)，\(T\) 为目标值——这是伪多项式（pseudo-polynomial）：复杂度对目标值的数值线性、对输入比特数是指数级。用 bitset 可把时间除以机器位宽 64。

边界。默认元素非负；若允许负数，可达和不再是 \([0, T]\) 的区间，改用有序集合维护可达和。target 为 0 返回 true；元素可重复出现但每件仍只用一次。

面试怎么讲。先声明「这是子集和问题，0/1 背包的判定版，伪多项式可解、一般化的维度下是 NP 完全的判定问题」——一句话定位问题的难度坐标，然后给 DP。倒序枚举的原因务必能讲清。

思路（先澄清口径）。「每天至多两部」是这道题最常见的面试口径：此时它就是载重量 3 的摆渡船问题——排序后双指针，最长的一部能否与最短的一部同天，能则配对，不能则最长者独占一天。配对策略的最优性可用交换论证：若最优解里最长的一部没和最短的同天，把它的同伴与最短的同伴交换不劣。若每天可连看任意多部，问题变成装箱（bin packing），是 NP 难问题，标准答复是首递减装箱（FFD）启发式：按时长从大到小依次放入第一个装得下的天，实践中接近最优。

代码（每天至多两部的双指针口径）。

int minDays(vector<int> d) {                   // 口径：每天 <= 3 小时、至多两部
    sort(d.rbegin(), d.rend());                // 从最长到最短安排
    int i = 0, j = (int)d.size() - 1, days = 0;
    while (i < j) {
        if (d[i] + d[j] <= 3) --j;             // 最长的一部带上一部最短的
        ++i; ++days;                           // 当天看完第 i 部（可能捎带了 j）
    }
    if (i == j) ++days;                        // 落单的最后一部
    return days;
}

手算 \([3.0, 2.5, 1.8, 1.5, 1.2, 0.9]\)（小时）：3.0 独占一天、2.5 独占一天、1.8 与 0.9 同天、1.5 与 1.2 同天，共 4 天；下界 \(\lceil 10.9 / 3 \rceil = 4\)，达到下界即最优。

复杂度。双指针 \(O(n \log n)\)（排序主导）；FFD 为 \(O(n \log n + nD)\)，D 为天数上界。

边界。任何一部超过 3 小时则无解（或按题意单独处理）；单部恰好 3 小时必须独占；用整数分钟存时长避免浮点比较误差。

面试怎么讲。第一句先问「每天最多几部」，这一句同时展示了澄清习惯与对问题难度谱系的判断（2 部 → 多项式，任意部 → NP 难）。然后用总时长下界去验证你的方案，是快速自查的好习惯。

思路。连续的空闲位置构成一段空隙；两个被占位置之间的空隙互不影响，可以各自填充。关键观察是：长度为 \(L\) 的空隙恰好能被 \(2\) 的幂铺满，且最省文件数的方案唯一——就是 \(L\) 的二进制分解。从大到小贪心（先放 \(2^{\lfloor \log_2 L \rfloor}\)，再递归余量）与二进制分解等价，因为每个 \(2^k\) 至多用一次（用了两次该幂就应合并成 \(2^{k+1}\)），而任何小于等于 \(L\) 的幂集合若要不重复地恰好凑出 \(L\)，只能是二进制表示里那些位。于是答案 = 各空隙长度的二进制中 1 的个数之和（popcount）。

代码。

long long countFiles(const string& slot) {    // '#' 已占用，'.' 空闲
    long long files = 0, run = 0;              // run：当前连续空隙长度
    for (char c : slot) {
        if (c == '.') ++run;
        else { files += __builtin_popcountll(run); run = 0; }
    }
    files += __builtin_popcountll(run);        // 收尾的空隙别漏
    return files;
}

例如 "#..##...#"：两段空隙长度 2 与 3，分别需要 \(2\)、\(2+1\) 个文件，共 3 个。

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。全占用返回 0；长度 0 的空隙 popcount 为 0 自动跳过；若空隙极长，popcount 用 64 位内建函数即可，或按位循环统计。

面试怎么讲。把「贪心从大到小」与「二进制分解唯一性」的等价说清楚是核心得分点；位运算（popcount）只是把结论翻译成代码。

思路。设 \(dp_{i,j}\) 为「以 \((i,j)\) 为右下角的最大全 1 正方形边长」。若 \(g_{i,j} = 1\)，这个正方形向左上三个方向同时受限，转移为三邻取最小再加一：

怎么读：边长为 \(d\) 的正方形以 \((i,j)\) 为右下角，等价于它的左边一格、上边一格、左上一格分别能撑起边长至少 \(d-1\) 的正方形；三者取最小就是瓶颈。答案是所有 \(dp_{i,j}\) 的最大值的平方。状态定义里的「右下角」与 Kadane 的「以 i 结尾」是同一种定语技术：让全局最优可枚举。

代码。

int maximalSquareArea(const vector<vector<int>>& g) {   // 返回全 1 最大正方形面积
    int m = (int)g.size(), n = (int)g[0].size(), best = 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (g[i][j] == 1) {
                if (i == 0 || j == 0) dp[i][j] = 1;          // 边界：只能自成一格
                else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                best = max(best, dp[i][j]);
            }
    return best * best;
}

复杂度。时间 \(O(mn)\)，空间 \(O(mn)\)，滚动一行后 \(O(n)\)。

边界。全 0 矩阵返回 0；单行单列时最大正方形至多边长 1；矩阵为空直接返回 0。追问「最大全 1 矩形（不是正方形）」时需要单调栈按行处理直方图，复杂度同为 \(O(mn)\)，可作为延伸提一句。

面试怎么讲。先画图说明三邻取 min 的含义（木桶效应），再给转移。被问「为什么不是 max+1」时，用反例回应：右上方向的空缺无法被三个邻居中任何一个看到。

思路。先算清一次交换的收益：交换相邻位置 \(i\) 与 \(i+1\)（权重 \(i+1\) 与 \(i+2\)），目标函数变化

即交换「降序对」（\(a \gt b\)）才有正收益——直觉上要让大数尽快拿到大权重，这与「整体排序后最大」一致。若题意是「总共至多交换一次」，答案就是 \(\max(0, \max_i (Arr_i - Arr_{i+1}))\) 加上原加权和。更常考的口径是每个元素至多参与一次交换：交换两两不相交，各对收益独立可加，问题变成「选出收益和最大的不相邻对」，即打家劫舍式的一维 DP：

手算 \([3,1,2,5,4]\)：各对收益 \(2, -1, -3, 1\)，选 \((3,1)\) 与 \((5,4)\) 两个不相交对，总增益 3；原加权和 \(51\)，优化后 \(54\)。

代码。

long long maxWeightedSum(vector<int> a) {      // 口径：每个元素至多交换一次
    int n = (int)a.size();
    long long base = 0;
    for (int i = 0; i < n; ++i) base += (long long)a[i] * (i + 1);
    if (n < 2) return base;
    vector<long long> g(n, 0);                  // g[i]：只考虑前 i+1 个位置的最大增益
    for (int i = 1; i < n; ++i) {
        long long gain = max(0LL, (long long)a[i-1] - a[i]);  // 交换 (i-1,i) 的收益
        g[i] = g[i-1];                         // 不动这一对
        if (i >= 2) g[i] = max(g[i], g[i-2] + gain);
        else g[i] = max(g[i], gain);
    }
    return base + g[n-1];
}

复杂度。时间 \(O(n)\)，空间可滚动到 \(O(1)\)。

边界。n 小于 2 无交换可言；所有相邻对都升序时增益为 0。面试第一句话应当是澄清「至多一次」是总共一次还是每个元素一次——两种口径答案不同，前者平凡、后者才需要 DP。

面试怎么讲。先推 \(\Delta = a - b\) 这一步初等代数（展示不慌），再指出「不相交交换 → 不相邻选择 → 打家劫舍模板」这条归约链。模板识别能力正是这类题的考点。

思路。源题对「操作」的定义语焉不详，面试第一步是澄清。取最常见的口径——操作为「把某元素折半（向下取整）」：每次操作的节省量是 \(x - \lfloor x/2 \rfloor = \lceil x/2 \rceil\)，它随元素变小而单调不增。于是贪心成立：每次都把操作花在「当前节省量最大」的元素上，用大根堆维护；交换论证——若最优解某次没操作堆顶元素，把它与堆顶交换后总节省不减。若口径是「元素减 1」，答案退化为 \(\sum a_i - k\)；若操作另有定义，贪心是否成立取决于节省量的单调性，这一点要在嘴上说明。

代码。

long long minSumAfterOps(vector<long long> a, long long k) {  // 操作：把某元素折半
    priority_queue<long long> pq(a.begin(), a.end());
    long long sum = 0;
    for (long long x : a) sum += x;
    while (k-- > 0 && !pq.empty()) {
        long long m = pq.top(); pq.pop();
        sum -= m - m / 2;                      // 本次操作省下 m - m/2
        pq.push(m / 2);
        if (m == 0) break;                     // 全部折到 0，再做也无收益
    }
    return sum;
}

例如 \([10, 6, 5]\)、\(k = 2\)：先折 10（省 5），再折 5（省 3），总和从 21 降到 13。

复杂度。\(O((n + k) \log n)\)。若元素取值有界，可用计数数组代替堆做到近似线性。

边界。k 大于「有收益的操作总数」时提前收工（元素全为 0）；元素可为 0 或 1（折半仍可能有益：1 折到 0 省 1）；负数元素的折半语义要先澄清——通常这类题限定非负。

面试怎么讲。把「先澄清操作定义」放在最前面，然后讲贪心的单调性条件与交换论证。题面残缺不是陷阱，是送分：看你有没有工程沟通的常识。

思路（可达集合分析）。每次交换恰好让 A「一进一出」：A 的元素个数不变，变化的只是值的集合。设 \(S_A\)、\(S_B\) 为两数组的不同值集合，\(d = n - |S_A|\) 是 A 中「多余副本」的个数（重复占位），\(f = |S_B \setminus S_A|\) 是 B 中 A 没有的值个数。要让 A 的不同值 +1，一次交换必须同时满足：换入一个不在 \(S_A\) 的新值、且被换出的元素是某个值的重复副本（换出唯一副本会让集合大小不变）。因此

三个瓶颈的含义：k 次操作的上限、重复副本的供给上限、新值的供给上限，且上限可达（每次挑一个重复副本与一个新值交换即可）。反过来问「最少能有多少个不同数」时，被迫交换可以逐个踢掉重数小的值，答案按「用 k 次把哪些值清出 A」贪心讨论。这道题考的不是代码而是集合进出的推理，白板上画两个圆（\(S_A\)、\(S_B\)）讲最清楚。

代码。

int maxDistinctAfterK(const vector<int>& A, const vector<int>& B, int k) {
    unordered_set<int> sa(A.begin(), A.end()), sb(B.begin(), B.end());
    int base = (int)sa.size();                 // A 原有的不同值个数
    int dup = (int)A.size() - base;            // A 中的多余副本数
    int fresh = 0;                             // B 中 A 没有的值个数
    for (int v : sb) if (!sa.count(v)) ++fresh;
    return base + min({k, dup, fresh});        // 三个瓶颈取最小
}

复杂度。时间 \(O(n)\)（哈希均摊），空间 \(O(n)\)。

边界。k 为 0 返回 \(|S_A|\)；A 全是重复值且 B 有大量新值时上限由 k 决定；若题目要求「恰好 k 次」，多出的被迫交换可能降低答案，口径又不同——照例先澄清。

面试怎么讲。「一进一出」四个字是全部建模。先给上界论证（每类瓶颈各一段），再给可达性构造，最后才落代码。这题代码极短，代码写长反而说明建模没做透。

思路。「前缀 + 划分点」：预处理总和，再从短到长枚举前缀长度 p（要求 \(p \lt n - p\)），用滚动的前缀和比较两边。找到的第一个满足条件的 p 即一个答案；若遍历完仍无，返回不存在。之所以从短前缀枚举，是因为「更短」的约束把 p 限制在前一半位置，天然剪枝。

代码。

// 返回前缀长度 p，使前缀更短（p < n-p）且和更大；不存在返回 -1
int splitShortGreaterPrefix(const vector<long long>& a) {
    int n = (int)a.size();
    long long total = 0, pre = 0;
    for (long long x : a) total += x;
    for (int p = 1; 2 * p < n; ++p) {          // 前缀长 p、后缀长 n-p，要求 p < n-p
        pre += a[p - 1];
        if (pre > total - pre) return p;
    }
    return -1;
}

例如 \([8, 3, 2, 1, 1]\)：p=1 时前缀和 8 已大于后缀和 7，返回 1。而 \([1,2,3]\) 枚举 p=1（约束 \(2 \times 1 \lt 3\)）失败后循环结束，不存在这样的划分。

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。\(n \le 1\) 无意义；全正递增数组常无解（前半又短又小）；注意题目若改为「任意划分子集（不要求连续）」则是子集和搜索，复杂度完全不同——先确认是前缀划分还是子集划分。

面试怎么讲。指出「前缀和 + 划分点」是这个题的模板名，一句话即可；把无解情形主动举例（递增正数组）体现边界意识。