算法设计范式
贪心算法
贪心算法一步一步地搭建解，并且在每一步都抓住此刻看起来最好的那个——局部最优的选择——而且从不回头反悔。想象给顾客找零、手里有一把硬币：你先递出仍然装得下的最大面额，再对剩下的金额递出装得下的最大面额，如此往复。这是最简单、最自然的策略，一旦它管用就快得出奇，往往排序之后只需扫一遍。
陷阱在于——而且是个大陷阱——此刻的最佳选择，未必是整体最佳方案的一部分。贪心只有在问题具备一种特殊性质时才正确：做出局部最优的选择永远不会断送通往全局最优答案的路（常称作贪心选择性质，与最优子结构并列）。在日常的美元/欧元币制下，「拿最大面额的硬币」总能给出最少枚数。但若自造一套币值为 {1, 3, 4} 的硬币去凑 6：贪心会先拿 4、再拿 1、再拿 1——三枚——而真正的最优是 3 + 3，只要两枚。同一个算法，换了数据，答案就错。
因此贪心设计讲究的是证明，而不只是「看起来对」：你必须论证这个贪心选择是安全的，或者找到一个反例把它推翻。在那些确实成立的地方，贪心是首选方法——霍夫曼编码通过反复合并出现频率最低的两个符号来构造最优前缀码；Dijkstra 最短路径与标准的最小生成树算法（Kruskal、Prim）骨子里都是贪心。当贪心失效时，通常的救兵是动态规划，它会权衡更多选项，而不是一看到顺眼的就立刻定下。
// Greedy change: always take the largest coin that fits.
int greedyCount(vector<int> coins, int amount) {
sort(coins.rbegin(), coins.rend());
int n = 0;
for (int c : coins)
while (amount >= c) { amount -= c; ++n; }
return n; // correct ONLY if the coin system is canonical
}面值 {1,3,4}、金额 6 时，贪心给出 4+1+1（3 枚）；最优是 3+3（2 枚）。
贪心与动态规划很容易混淆：两者都需要最优子结构，但贪心在每一步只认定一个选择、绝不回头，而动态规划会保留若干候选答案、让表格来定夺。如果你没法证明贪心的选择是安全的，就转用动态规划。
又称
另见