贪心再回顾 · 考级冲刺

贪心：每一步都选当前看起来最好的，不回头、不反悔。代码通常很短，但正确性全靠一句话——「为什么这样选一定不会更差」。说不清这句话，贪心就可能翻车。

找零钱是经典的「贪心不一定对」例子。面值 ${1, 5, 10, 25}$ 时，每次尽量用大面值，贪心正确；但换成 ${1, 3, 4}$ 凑 6，贪心先拿 4，再拿两个 1，共 3 枚；最优其实是 $3 + 3$ ，只要 2 枚。贪心在这里就错了。

// 贪心找零（只对特定面值体系成立！）
int coins[] = {25, 10, 5, 1};
int cnt = 0, money = 63;
for (int c : coins) {
    cnt += money / c;   // 尽量多用当前大面值
    money %= c;
}

判断能不能贪心：（1）能证明「贪心选择性质」——存在一个最优解包含当前这一步的贪心选择；（2）能拆成子问题（最优子结构）。证不出来就老实用动态规划兜底。

考试常见坑：（1）样例过了不等于贪心对，要会构造反例；（2）不确定时 DP 更稳；（3）很多贪心要先排序，见下一节。