贪心算法是什么？并不是字面上贪心的意思，而且选出目前最好的结果，这块有个误区，并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都能得到最优的结果，但对许多问题它能产生某个条件下整体的最优解。如最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的相似或相近结果。

当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

本篇通过基本思想和实例分析进行贪心算法的了解和认知，“贪心”二字顾名思义，因此其规律特征就是更加注重当前的状态，贪心法做出的选择是对于当前所处状态的最优选择，它的解决问题的视角是微观的“局部”，而不是从全局宏观的角度思考和看待问题，根据这样的性质，要求贪心法解决的问题有“无后效性”——当前的决策不会影响到后续的决策，因为如果问题前后勾连紧密的话，会造成求解过程十分混乱。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。

一、贪心算法基本思想

（1）基本概念

1. 最自然智慧的算法；

2. 用一种局部最功利的标准，总是能做出在当前看来是最好的选择；

3. 难点在于证明局部最优解最功利的标准可以得到全局最优解；

4. 对于贪心算法的学习主要是以增加阅历和经验为主。

（2）简介

贪心算法（英语：greedy algorithm），是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

二、贪心算法求解思路

（1）标准求解过程

1. 分析业务

2. 根据业务逻辑找到不同的贪心策略

3. 对于能举出反例的策略，直接跳过，不能举出反例的策略要证明有效性，这往往是比较困难的，要求数学能力很高且不具有统一的技巧性

（2）贪心算法解题套路

1. 实现一个不依靠贪心策略的解法X,可以用暴力尝试

2. 脑补出贪心策略A,贪心策略B,贪心策略C…

3. 用解法X和对数器，用实验的方式得知哪个贪心策略正确

4. 不要去纠结贪心策略的证明

（3）常见题型及解题方法

1. 常见题型

“我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。”

“我们每次都取 XXX 中最大/小的东西，并更新 XXX。”（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

2. 排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

3. 后悔解法

思路时无论当前的选项是否是最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃这个选项，否则就正式接受，如此往复。

4. 与动态规划的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

三、贪心算法实例讲解

例题一：居民楼路灯问题

给定一个字符串str，只由‘X’和‘.’两中国字符构成。

‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。

如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所需要点亮的位置，至少需要几盏灯

例如： X…X…X…X. 需要至少5盏灯