note/algorithm/9、贪心算法.md

## <center>贪心算法</center>

### 贪心算法

* 1）最自然智慧的算法
* 2）用一种局部最功利的标准，总是做出在当前看来是最好的选择
* 3）难点在于证明局部最功利的标准可以得到全局最优解
* 4）对于贪心算法的学习主要以增加阅历和经验为主

### 贪心求解的标准过程

* 1，分析业务
* 2，根据业务逻辑找到不同的贪心策略
* 3，对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性这往往是特别困难的，要求数学能力很高且不具有统一的技巧性

### 贪心算法的解题套路

* 1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
* 2，脑补出贪心策略A、贪心策略B、贪心策略C...
* 3，用解法X和对数器，用实验的方式得知哪个贪心策略正确
* 4，不要去纠结贪心策略的证明

### 贪心算法常见问题

#### 最小字典序

&emsp;&emsp;给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。
&emsp;&emsp;a.b&lt;b.a并且b.c&lt;c.b 得到a.c&lt;c.a，比较的传递性。

#### 分割金条

&emsp;&emsp;分割金条，60长度分成10、20、30。一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?

&emsp;&emsp;例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。

&emsp;&emsp;输入一个数组，返回分割的最小代价。暂不考虑切割的顺序，如果考虑切割顺序需要使用动态规划和四边形不等式。

&emsp;&emsp;暴力尝试，双层循环将i和j合并，递归得到花费，最后将最小的花费返回。

&emsp;&emsp;将所有分割后的长度放入小根堆，每次获取两个长度相加然后放回小根堆，重复直到小根堆只剩一个元素。
&emsp;&emsp;每次都切割最大长度的反例97、98  和  100、99。正确操作是第一次切割成100+99和98+97，而不是切割成100和99+98+97。<font color="red">反例的证明就是哈夫曼编码。</font>

#### 点灯

&emsp;&emsp;给定一个字符串str，只由‘X’和‘.’两种字符构成。‘X’表示墙，不能放灯，也不需要点亮。‘.’表示居民点，可以放灯，需要点亮。如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮。返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。

#### 安排会议室

&emsp;&emsp;一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。

#### IPO

&emsp;&emsp;输入: 正数数组costs、正数数组profits、正数K、正数M
&emsp;&emsp;costs[i]表示i号项目的花费
&emsp;&emsp;profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
&emsp;&emsp;K表示你只能串行的最多做k个项目
&emsp;&emsp;M表示你初始的资金
&emsp;&emsp;说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
&emsp;&emsp;输出：你最后获得的最大钱数。