数据结构 04：从查找和排序走到动态规划

算法不只是一个函数名。它首先规定输入满足什么条件，然后定义每一步如何改变状态，最后说明为什么停止时就是答案。本篇用三个案例说明这个思路：找第一个不小于目标的数；把无序记录排好；用最少硬币凑出金额。

每节先观察数据变化，再穿插不变量、复杂度和边界条件。配套完整 C++17 程序包含独立对照测试；学习路线说明运行方式。

一、二分查找：维护一条分界线

从重复值开始

有序数组 [1,3,3,5,8]，目标是 3。我们要返回第一个不小于 3 的位置，也就是下标 1。这个问题比“找到任意一个 3”更明确：即使不存在 3，也能告诉我们应该插在哪里。

初始 lo=0, hi=5。取 mid=2，值为 3，说明分界线可能就在 mid，也可能更靠左，所以令 hi=2。再取 mid=1，值仍为 3，令 hi=1。最后 mid=0 的值为 1，确定它在分界线左边，令 lo=1，结束。

这里维护两个不变量：

• [0,lo) 中的数全部小于 target。
• [hi,n) 中的数全部大于等于 target。

尚未检查的元素在 [lo,hi) 中；可能的分界位置允许等于 hi，最终也可能是 n。当 lo=hi 时，两边已经接上，这个位置就是答案。

std::size_t lower_bound_index(const std::vector<int>& a, int target) {
    std::size_t lo = 0, hi = a.size();
    while (lo < hi) {
        const auto mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

注意 hi 不是最后一个有效下标，不能无条件读取 a[hi]。判断“是否真的找到 target”还需要：

const auto i = lower_bound_index(a, target);
const bool found = i < a.size() && a[i] == target;

空数组返回 0；所有值都小于目标时返回 n；所有值都大于目标时返回 0。短路求值保证 i==n 时不会读越界。

排序的成本由谁承担

二分的前提不是“拿到一个数组”，而是满足相应比较条件的分区。这里使用升序排列的 vector，既满足前提，又能 O(1) 到达 mid，因此总查找成本 O(log n)，额外空间 O(1)。

如果只查询一次无序数组，先花 O(n log n) 排序再二分，未必优于一次 O(n) 顺序扫描。若数据保持有序并要反复查询，二分的价值才会逐渐体现。

通用 std::lower_bound 可以接收前向迭代器，但在链表上移动到中点并非常数成本：比较次数仍是对数级，迭代器递增总数可能线性。使用有序树容器时优先调用它自己的 lower_bound 成员函数。相关前提和复杂度可核对 C++ 标准草案 binary.search。

目标为 4 时返回下标 3：此处的 5 是第一个不小于 4 的值；“返回了一个位置”并不意味着目标存在。

二、插入排序：让有序区域每次长一格

待排序序列 [5,2,4,1]。先把第一个元素看成已经排好，后面逐个取出，插入前面的有序区域。

右移期间数组里暂时有重复值，因为一个值已保存在 key 中，原位置可用作“空位”。别把这段中间状态误判为数据丢失；应检查“key 加数组中尚有效的元素”是否仍包含全部记录。

for (std::size_t i = 1; i < a.size(); ++i) {
    const auto key = a[i];
    auto j = i;
    while (j > 0 && a[j - 1] > key) {
        a[j] = a[j - 1];
        --j;
    }
    a[j] = key;
}

每轮开始时 [0,i) 有序；移动只挪走比 key 大的值，所以 key 落位后 [0,i+1) 有序。j>0 必须先检查，避免无符号下标减一溢出后越界。

为什么等号决定稳定性

两条记录键相同但身份不同，例如 (2,A),(2,B)。条件使用 > 时，后来的 B 不会越过相等的 A，排序稳定。若改成 >=，B 可能被插到 A 前面，稳定性就被破坏。

已排序输入只需线性比较；逆序输入需要平方级移动，最坏 O(n²)。就地保存一个 key，额外空间 O(1)。这让它很适合观察排序机制和小规模数据，却不是任意大数组的通用首选。

怎样选择常用排序

需要相同键的记录保留原顺序时考虑 std::stable_sort。标准草案对 sort 和 stable_sort 分别给出约束；后者的比较界还与可用额外内存有关，不要把所有排序函数都简写成相同的时空复杂度。

三、动态规划：为什么“先拿大的”会输

硬币面值是 [1,3,4]，每种可用任意枚，目标金额 6。

每次优先取最大的面值，会得到 4+1+1，用了 3 枚。但是 3+3 只要 2 枚。这是贪心规则的反例：某一步看起来最有利，不能自动推出整体最优。

先把状态说完整

令 dp[x] 表示恰好凑出金额 x 的最少硬币数。这个定义只适用于面值为正整数、每种数量不限、目标为非负整数的问题。若每枚只能用一次，需要不同的状态或更新顺序。

最后一枚硬币可能是任意 c≤x。去掉它，前面的硬币必须恰好凑出 x−c，于是：

$$dp[0]=0,\qquad dp[x]=\min_{\substack{c\in C\\c\le x\\dp[x-c]\ne\infty}} \bigl(dp[x-c]+1\bigr).$$

没有合法前驱时就保持不可达。正面值保证 x−c<x，因此从小金额向大金额填写时，前驱已经算完。

算 x=6 时，最后拿 1 得 dp[5]+1=3；最后拿 3 得 dp[3]+1=2；最后拿 4 得 dp[2]+1=3，因此选 2。

为什么这个递推确实最优

假设金额小于 x 的最优值都已算对。任意一个凑出 x 的方案都有最后一枚 c；如果余下方案不是 x−c 的最优方案，就能换成更少枚的方案，使总数更少。因此最优解一定出现在所有“最优前驱 + 最后一枚”的候选中，取最小值即可。

这就是最优子结构。用表保存前驱答案，避免反复求相同子问题；同时它也给出了实现的依赖顺序，而不是单纯“为了提速加个数组”。

从枚数恢复硬币方案

当某个候选改进 dp[x] 时，另存 last[x]=c。从目标开始，反复输出 last[x]，再令 x-=last[x]，直到 x=0，就得到一个最优方案。相同最少枚数可能有不同组合，此实现返回其中之一。

完整代码用 std::optional 区分“不可达”和“合法的 0 枚”。C=[4,6], amount=5 返回不可达；空面值集合和金额 0 返回空方案。拒绝负目标、非正面值；金额过大时直接给出输入限制错误，避免示例无限分配内存。不可达的标记不参与 INF+1 运算，防止溢出。

面值种类数为 m，金额为 A，时间 O(mA)，空间 O(A)。这相对于 A 的数值线性；如果按输入金额的二进制位数衡量，它属于伪多项式时间。金额非常大时不能只看到“线性”就认为一定高效。

使用 [2,5] 时，金额 6 的答案是 3 枚 2，金额 3 则不可达。若改成“每枚只用一次”，状态与更新顺序也需要改变，见动态规划的状态与恢复。

四、把三个算法放到同一个框架里

再回看结构篇中的 BFS，也可以从同样角度理解：状态是已发现集合、队列和距离；每轮处理一个顶点，发现未访问的邻居。无权图按层展开，第一次到达就是最短边数；有不同边权时不能直接沿用这个结论。

本篇程序用标准库校验 lower_bound，用带身份的记录校验稳定性，用“金额图上的 BFS”独立校验小规模硬币结果。测试不是把同一份递推再抄一遍，而是用另一种方法寻找反例。

继续阅读：序列处理、分治、回溯与贪心、动态规划、图算法。