贪婪算法是五大常用算法之一，需要掌握，本文会详细介绍贪婪算法的基本思想及其代码实现例子@mikechen
贪婪算法定义
贪婪算法，英文名为Greedy Algorithm，又名贪心算法。
贪婪算法，是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
贪婪算法原理思想
贪婪算法的基本思路，主要分为如下三步：
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。
贪婪算法的应用场景
简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就可以使用贪婪算法。
比如：贪婪算法可以解决一些最优化问题，如：求图中的最小生成树，求哈夫曼编码等。
贪婪算法经典例子
1.找零钱的例子
1）题目
指定币值和相应的数量，用最少的数量凑齐某金额。
2）思路
利用贪婪算法，基本思路：我们优先选择面值大的钱币，以此类推，直到凑齐总金额。
3）算法实现
2.活动选择例子
1）题目
有这么一堆数，按照金字塔排列下来，如下图所示：
我们从顶点开始，求从顶部到底部的最大路径之和。
2）思路
利用贪婪算法，基本思路：要是用眼瞅，比较容易能看出来最佳路径是9-7-3-4-5，但是如果数一多，眼瞅就不好使了，此时就得靠代码去算。
3）算法实现
// 注意，下面的代码只是表意，不能直接扒过去用
// a[i][j]表示数组，maxJ表示数组的最大层数，temp表示临时数值
// maxJ表示总列数，maxI表示当前列的最大行数
for(j=0; j<maxJ; j++){
for(i=0; i<maxI; i++){
temp1 = a[i][j] + a[i][j+1];
temp2 = a[i][j] + a[i+1][j+1];
temp = max(temp1, temp2);
}
maxSum = maxSum + temp;
}
return maxSum;
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》