贪心算法
顾名思义，贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
在面临选择时，贪心算法都作出对眼前来讲最有利的选择，不考虑对将来的不良影响，每个选择一旦做出，不可更改，不允许回溯，根据不同的贪心策略，贪心算法就不同，贪心解的质量也不同，所以贪心策略很重要。
可以看出，此算法思想很简单，具有高效性，但不一定得出最优解。
贪心算法的基本思路，主要分为如下4步：
基本思路：
1）建立数学模型来描述问题；
2）把求解的问题分成若干个子问题。
3）对每一子问题求解，得到子问题的局部最优解。
4）把子问题的解局部最优解合成原来解问题的一个解。
分治算法
分治算法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解。
分治算法，大致分为如下三个步骤：
1）分解
将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
2）求解
若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
3）合并
将各个子问题的解合并为原问题的解。
动态规划算法
动态规划算法，英文名Dynamic Programming，是一种把原问题分解为相对简单的子问题以求解的方法。
动态规划算法是把原问题分解为若干子问题，自底向上，先求解子问题，把结果存储在表格中。
在求解大问题时直接从表格中查询小问题的解，避免重复计算，从而提高算法效率。
动态规划算法通常用于求解具有某种最优性质的问题，在这类问题中，可能会有许多可行解。
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治算法不同的是，适合于用动态规划算法求解的问题，经分解得到子问题往往不是互相独立的。
动态规划的设计都有着一定的模式，一般要经历以下4个步骤：
1）划分阶段
按照问题的特征，把问题分为若干阶段，划分后的阶段一定是有序的或者可排序的。
2）确定状态和状态变量
将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性。
3）确定决策并写出状态转移方程
状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程。
4）寻找边界条件
状态转移方程是一个递推式，因此需要找到递推终止的条件。
搜索算法
搜索法包含穷举搜索，深度优先搜索，广度优先搜索，回溯法，分支限界法，其实这些算法的基础就是穷举搜索，只是加上一定的原则来优化过程，就形成了后面的几种算法。
回溯法就是在深度优先搜索的基础上允许回溯，分支限界法是在广度优先搜索基础上允许剪枝，学习时主要学习思想，这些算法名字不要太在意。
近期新算法
①遗传算法
从达尔文的生物进化论中得到启发，借鉴自然选择和进化的原理，模拟生物在自然界的进化过程所形成的一种优化求解方法，遗传算法从代表问题的可能潜在解集的一个种群出发，一个种群有一定数量的个体组成，每个个体实际上是染色体带有特征的实体，每一代根据个体的适应度大小挑选个体，并借助遗传算子进行交叉和变异，得到近似最优解。
②模拟退火算法
他的出发点是物理中固体的退火过程与一般组合优化之间的相似性，固态物质退火时，通常先加温，使其中的粒子自由游动，然后逐渐降低温度，粒子也逐渐形成低能态的晶格，最终形成最低能量的基态。所以他从某一较高初温开始，伴随温度参数的不断下降重复抽样，最终得到全局最优解，他是基于概率的。
③蚁群算法
蚁群算法是模拟自然界蚂蚁觅食过程的一种分布式，启发式群体智能算法，用于求解复杂的组合优化问题，如TSP,JSSP,GCP等问题。
递归算法
递归算法就是：一个方法在执行过程中调用自身, 就称为 “递归”。
递归的常用算法伪代码如下：
func( mode){
if(endCondition){ //递归出口
end;
}else{
func(mode_small) //调用本身，递归
}
}
采用递归描述的算法通常有这样的特征：
1）为求解规模为N的问题，设法将它分解成规模较小的问题；
2）然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。
3）这样的分解方法具有收敛性。即存在一个递归返回状态。
迭代法
也称辗转法，是一种不断用变量的旧值递推新值的过程。
最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。
利用迭代算法解决问题，需要做好以下三个方面的工作：
1）迭代变量：在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
2）迭代关系：指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
3）迭代过程：迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
迭代法都可以转为递归法。迭代法可以理解为具有递归性质的非递归解法。当然，非递归解法还可利用栈的思想。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》