贪心会翻车

贪心并非万能，有时会给出错误答案。看一个反例：硬币面值是 $1,3,4$，要凑 $6$ 元。

贪心“先拿最大”：拿 $4$，剩 $2$；再拿两个 $1$，共 $4+1+1=3$ 枚。但更优解是 $3+3=2$ 枚！贪心因为一开始贪那个 $4$，反而错过了最省方案。

// 真正保证最优要用动态规划
int dp[7];
dp[0] = 0;
for (int i = 1; i <= 6; i++) {
    dp[i] = 1e9;
    for (int c : {1, 3, 4})
        if (i >= c) dp[i] = min(dp[i], dp[i-c] + 1);
}
// dp[6] == 2，才是正确答案

原因在于：面值 $1,3,4$ 不满足贪心成立的条件，局部“拿最大”不再能推出全局最优。

结论：用贪心前一定要确认它对这道题真的成立——最好能证明，或用小数据和暴力/DP 对拍验证。不确定时，宁可用一定正确的动态规划，也别赌贪心。这是考试里极常见的失分点。