贪心（Greedy）¶
贪心算法是一种在每一步选择中都采取当前状态下的局部最优解，从而希望通过一系列局部最优选择达到全局最优或近似最优的算法。
基本思想¶
- 每一步都做出在当前看来最优的选择（即“贪心”）。
- 不回溯、不考虑整体，只关注当前决策。
示例（跳跃游戏）¶
判断是否能从数组起点跳到终点。
for (int i = 1; i <= n; i++) {
if (i > farthest) {
cout << "NO" << endl;
return 0;
}
farthest = max(farthest, i + a[i]);
}
cout << "YES" << endl;
注意事项¶
- 贪心算法不一定总能得到最优解，需证明问题具有贪心性质。
- 有些问题需结合动态规划或其他方法解决。
应用场景¶
- 跳跃游戏
- 零钱兑换问题
- 最小生成树（Prim/Kruskal）
- Dijkstra 最短路\ ……