# 进阶算法-贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略**必须具备无后效性**，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
注意：贪心算法需要针对不同的case选择不同的策略，不一定你选择的策略就是最贪的，即使不是最贪策略，也不能说当前的贪心策略不对，贪心策略需要大量的数据去验证和迭代，逼近最优解。所以贪心，关键是一种算法思想。
# 1、最大利润
- 策略1：从最低点买入，在最高点卖出（追求单次利益）；
- 策略2：从低点买入，只要可以赚钱就卖出；不断买卖（追求多次利益，单次利益不够）；
- 策略3：从低点买入，到价格高点卖出，不断买卖（在保证单次利益的基础上，实现多次交易）；
前两种策略都不够贪，3最贪。
股票买卖问题也可以参考动态规划公式来求解： 动态规划 DP-table 公式 (opens new window)
# 2、找零钱
- 策略1：给钱找零，不区分金额直到找到足够的金钱（追求单次找零）；
- 策略2：给钱找零，优先给金额大的零钱，尽量把零钱放在手里（追求多次找零）；
策略2更贪，因为可以保留更多零钱在手里。