最优子结构：贪心算法能成功的“体检单”

贪心算法就像一位急性子的同学，总想在每一步都选当下最好的选项，然后拍拍胸脯说：“这样走下去，结局一定最好！”但问题来了——贪心算法凭什么觉得自己能成功？ 原因就在于它需要先通过一场“体检”。这场体检要检查的关键项目就是 最优子结构（Optimal Substructure）。简单说：如果原问题的最优解，可以拆成若干个子问题的最优解来拼接，那么这个问题就拥有最优子结构。就像你拼乐高，车身拼得最稳，轮子装得最牢，最终整辆车才能跑得最快——每个小部分都做到最好，整体才能做到最好。

贪心算法之所以敢“走一步看一步”，就是因为它相信：只要当前这一步选得最好，剩下的子问题也能用同样的方法选得最好，最终拼起来就是全局最优。那么，这个“相信”到底对不对？体检报告说了算。

什么是最优子结构？——用生活小事理解

先来看两个生活中的例子，帮你快速感受什么是最优子结构。

✅ 例子1：买零食凑钱（正例）

小明有5元、10元、20元三种纸币，他想买一包15元的薯片，并且希望用最少的纸币付钱。最优解是：一张10元 + 一张5元，共2张。
这个问题的子问题是：如果先付一张10元，剩下的5元就是子问题（用最少的纸币凑5元），而凑5元的最优解就是一张5元。把子问题的最优解（1张5元）和第一步的选择（1张10元）拼起来，就得到了原问题的最优解（2张）。
这说明凑钱问题（当纸币面额特殊时）具有最优子结构。

❌ 例子2：考试复习（反例）

小红期末要考数学和语文两门，她总复习时间只有2小时。数学每复习1小时能提高10分，语文每复习1小时能提高8分。她的目标是总分最高。
如果贪心：先选短时间内提分最多的科目——数学，复习1小时得10分；剩下1小时再复习语文得8分，总和18分。但最优方案可能是数学和语文各复习1小时？其实这里数学和语文的提分是独立的，分开最优就是整体最优，所以贪心成功。但如果换成不能同时复习两门，或者复习时间有重叠，贪心就可能失败。但这里只是想说明：最优子结构要求子问题之间互不影响。

最优子结构和贪心选择性质——一对“好兄弟”

记住这句话：最优子结构是贪心算法的必要条件，但不是充分条件。也就是说，一个问题有了最优子结构，贪心算法未必就能成功，还需要另一个条件——贪心选择性质。

• 最优子结构：问题可以分解，子问题的最优解能拼成全局最优解。
• 贪心选择性质：你选的当前这一步，就是通往全局最优的第一步。换句话说，你可以先做出一个看似局部最优的选择，然后相信剩下的子问题也能用贪心得到最优。

可以把贪心算法想象成：  
- 最优子结构 = 你相信拼好每一块乐高后，整体模型就是最好的。  
- 贪心选择性质 = 你知道当下该选哪一块乐高（比如先拼底座），而且选了这块之后，剩下的部分依然能拼成最好的模型。

反例回顾：硬币找零[1,3,4]找6元

还记得之前的硬币找零问题吗？用[1, 3, 4]三种面额的硬币找零6元，贪心会怎么做？先拿最大的4元，剩下2元，再拿两个1元，一共用了 3枚硬币 (4,1,1)。但最优解其实是两个3元硬币，只用 2枚。这里贪心失败了！为什么？因为问题虽然具有最优子结构（找零2元的最优解是2个1元，找零6元的最优解可以从子问题构造），但不具有贪心选择性质——当前选最大的4元，并不是全局最优的第一步。所以贪心掉进了陷阱。

如何判断一个问题有没有最优子结构？

你可以用下面几个“体检指标”来检查：

1. 分解性：问题能不能拆成若干个更小的同类问题？比如“找零n元”可以拆成“先选一枚硬币，然后找零剩下的钱”。
2. 独立性：子问题之间不会互相影响。比如活动安排中，选了活动A后，剩下的活动只需要在A结束后的时间选，与A之前无关。
3. 最优性：如果子问题不是最优的，那么拼起来的大问题也不可能是最优的。
4. 剪贴法验证：假设你有一个全局最优解，把它切开，检查每一块是不是子问题的最优解。如果不是，你可以用子问题的更优解替换它，从而得到更大的全局最优——这就矛盾了，说明原假设不成立，所以子问题也一定是最优的。

对于中小学生，记住一条简单口诀：

如果一个问题能切成相同的更小块，并且小块的最优解拼起来就是大块的最优解，那么它就具备最优子结构。

生活例子：收集奥特曼卡片

小明想收集一套10张不同的奥特曼卡片，他每天去抽卡，每次花1元抽一张（假设每张卡出现概率相等）。他希望能用最少的钱集齐所有卡片。这个问题有最优子结构吗？
拆解：先抽到一张新卡，然后剩下的问题变成集齐剩下的9张卡。如果子问题（集齐9张）的最优解是m元，那么加上第一次抽卡的钱，就是原问题的候选解。但注意，第一次抽卡可能重复，所以子问题不是完全独立——子问题的最优解依赖于当前拥有哪些卡。但整体上，这个问题的确具有最优子结构（可以用动态规划求解）。不过贪心算法（比如每次都抽最新的一张）并不一定得到最少钱数，所以它没有贪心选择性质。

常见错误：新手最容易踩的坑

错误1：以为只要问题能拆分就能用贪心

纠正：拆分后必须满足“子问题的最优解能拼出全局最优”。比如数字拆分问题：将正整数n拆成若干个数的和，使乘积最大。贪心地拆成尽可能多的3会得到最优吗？有时会，但需要验证。

错误2：混淆最优子结构和贪心选择性质

纠正：有些问题有最优子结构但没有贪心选择性质（如上面硬币找零），贪心就不行。两者缺一不可。

错误3：忘记贪心算法需要排序或选择规则

纠正：即使问题满足条件，贪心策略也要选对“局部最优”的标准。比如活动安排中按结束时间最早选，而不是按开始时间最早。

完整示例：活动安排问题（贪心成功的经典）

活动安排问题是贪心算法成功的典型代表。假设有多个活动，每个活动有开始时间和结束时间，一个人只能同一时间参加一个活动，问最多能参加多少个活动。
贪心策略：先选结束时间最早的活动，然后从剩下的活动中选与它不冲突且结束时间最早的，以此类推。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start;   // 开始时间
    int finish;  // 结束时间
};

// 按结束时间从小到大排序
bool cmp(Activity a, Activity b) {
    return a.finish < b.finish;
}

int greedyActivity(vector<Activity>& acts) {
    sort(acts.begin(), acts.end(), cmp);  // 排序：按结束时间升序
    int count = 1;                       // 至少选第一个活动
    int last_end = acts[0].finish;       // 记录最后一个选中活动的结束时间

    for (int i = 1; i < acts.size(); i++) {
        if (acts[i].start >= last_end) { // 如果当前活动开始时间 >= 上次结束时间
            count++;
            last_end = acts[i].finish;   // 更新结束时间
        }
    }
    return count;
}

int main() {
    // 活动列表：{开始, 结束}
    vector<Activity> acts = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8},
        {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}
    };
    cout << "最多可以参加的活动数: " << greedyActivity(acts) << endl;
    return 0;
}

输出：

最多可以参加的活动数: 4

这个问题的最优子结构体现在：如果你选择了第一个结束的活动，那么剩下的问题就是在该活动结束后开始的所有活动中，找最多不冲突活动；子问题的最优解加上第一个活动，就是原问题的最优解。同时，选择最早结束的活动也满足贪心选择性质，所以贪心能成功。

小结与相关指引

• 最优子结构是贪心算法的“健康指标”，它告诉我们问题可以被分解成小问题，并且小问题的最优解能组成大问题的最优解。
• 贪心选择性质是另一个必要条件，它告诉我们当前这一步选什么才能一步步走向最佳。
• 如果问题同时具备这两个条件，贪心算法就能一步到位、又快又好；如果只有最优子结构而没有贪心选择性质，就需要用动态规划（比如硬币找零的通用解法）。

想更深入了解？

• 可以看《动态规划入门》，它也是依赖最优子结构，但通过“尝试所有选择”来保证最优。
• 再学《贪心算法的经典应用》，比如哈夫曼编码、最小生成树、最短路等，那里有更多成功例子。
• 也可以挑战自己：想一想“排队打水”问题（每个人打水时间不同，如何安排顺序使总等待时间最短）——它有没有最优子结构？贪心又该怎么选？

记住：下次想用贪心解决问题，先拿出“体检报告”——检查最优子结构和贪心选择性质。两项合格，大胆用；否则换思路，别硬闯！