大多数算法基于以下4种算法： （1）贪心算法； （2）分治算法（递归）； （3）动态规划（DP）； （4）穷举。 现在说贪心算法。
贪心算法主要思路是： （1）把求解的问题分成若干个子问题； （2）对每个子问题求解，得到子问题的局部最优解； （3）把子问题的局部最优解合成原来问题的一个解。
从网上搜索贪心算法，基本都能搜到下面这段：
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
就是说，贪心算法所得出的解，不一定是全局最优解。初看不理解，为啥得不到全局最优解呢？看过别人写的文章才知道，这跟子问题最优解的选择有关。贪心算法其实是动态规划（DP）的一种特殊情况，它的关键词是“局部最优”，每次只做当前对于自己最“有利”的选择，而动态规划则是要寻找“全局最优”，并且一定能找到“全局最优解”。
简言之，贪心算法比较符合人的思维，即每次都选择最有利于自己的选项，不考虑其他方面，也不考虑未来会怎样。
既然贪心算法都不能保证得出全局最优解，为什么还要用它呢？因为如果直接求解全局最优解，可能时间复杂度和计算量都过于庞大，那么可以退而求其次，牺牲全局最优解来换取省力，不要求一定要得出全局最优解，只要趋近于最优解就可以。就像本来我应该拿100元工资（全局最优解）的，但是要大费周折，我还可以选择拿99块钱工资（局部最优解），却可以省下大量的精力，虽然钱少了，但我未尝不乐意。
“对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。”即求解一个问题能否用贪心算法，要看此问题的最优解是否能从子问题的最优解中得出来。判断一个问题是否适用贪心算法的难点就在于此，你想用贪心算法，又不能保证得出的解一定是整个问题的最优解，那肯定不合适啊。使用贪心算法只能尽可能地去求解趋近于全局最优解的解。
有1毛、5毛、1元、5元、10元、20元、50元、100元的人民币若干，现在想要拿出267.3元支付，要求纸币的张数要最少，应该怎样选择？生活常识告诉我们，应该从面额大的往小的一步步来选。先选两张100的，再选一张50的，再选一张10元的，再选一张5元的，再选两张一元的，最后选三张1毛的。这每一次选择都是一个子问题，都进行了一次贪心算法，即在不能超过总金额的前提下，每次都优先选择面值最大的人民币。
题目来源于Leetcode第122题：买卖股票的最佳时机 II
描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
题目很好理解，下面用贪心算法的思路来分析。
1.题目的全局最优解是：最大化的利润。 2.把总问题分解为子问题：每次只考虑今天买明天卖能不能获利，只要能获利，那我今天就买，不考虑以后的事。 3.子问题最优解合成全局最优解：每个子问题获得的利润加起来就是最大化的利润。
代码也很简单，就6行：
class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); int sum = 0;//总利润 for(int i=0;i < len-1;++i){ if(prices[i+1]-prices[i] > 0) sum += prices[i+1] - prices[i]; } return sum; } };是Leetcode题目，见我的博客解体思路2，传送门->53.最大子序和 另一道：->455.分发饼干
最后，欢迎留言批评指证。
