分治算法包括

1. 分治、贪心五大算法

1、分治
分治（即分而治喊孙之），把一个复杂的问题分成多郑激链个相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
适用场景：二分搜索、归并排序、快速排序、大整数乘法、第K小元素、最近点对、快速傅里叶变换等。

2、动态规划
动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划通常用来求最优化问题。此类问题可以有很多可行解，我们求出的是一个最优解，可能存在多个最优解。（最优子结构、公共子问题）
与分治法的区别是：分治的子问题是相互独立的，动态规划最好解决有公共子问题的，子问题相关性很大。
使用场景：矩阵连乘、钢条切割、最长公共子序列、最优二叉搜索树、流水作业调度、0/1背包问题等。

维特比算法是动态规划在HMM中的应用，维特比算法用于解决HMM的预测或者叫解码问题。
viterbi有最优解是因为HMM每一步是条件独立的！既然后面的概率和前面的没关系，那前面选最大的概率就行了。
而beam search时后面的概率依赖于前面所有的词，相当于n-gram是满的，viterbi的n-gram是2

背包问题：
https://blog.csdn.net/wind__chaser/article/details/89457771
https://blog.csdn.net/qq_38410730/article/details/81667885

3、贪心
通过局部最优选择达铅吵到全局最优选择。贪心算法不一定总产生最优解，贪心算法是否产生优化解，需严格证明贪心算法产生最优解的条件：（最优子结构、贪心选择性）
贪心选择性：当一个问题的全局最优解可以通过局部最优解得到，称这个问题具有贪心选择性。
适用场景：活动选择问题、哈夫曼编码问题、最小生成树问题、单源最短路径问题等。

贪心算法：softmax之后取最大概率。与之对应的是，Beam Search算法
http://www.360doc.com/content/18/0618/09/17563728_763230413.shtml
https://blog.csdn.net/qq_16234613/article/details/83012046
https://www.hu.com/question/54356960

分治和动态规划的区别：
动态规划也是一种分治思想（比如其状态转移方程就是一种分治），但与分治算法不同的是，分治算法是把原问题分解为若干个子问题，
自顶向下求解子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原始问题分解为若干个子问题，然后自底向上，
先求解最小的子问题，把结果存在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

动态规划和分治法有些相像，都是把一个问题分成了很多子问题来求解，但是不同的是动态规划会记忆之前解决的子问题的结果，
避免了重复计算。判断一个问题是否能用动态规划求解，要看它是否能划分成合适的子问题，然后写出递推关系式。
动态规划得到的解一定是最优解。

2. 分治算法几个经典例子

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础。

图二

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔

3. 每天一个知识点：分治算法：选择问题

选择问题的要求是找出含有 N 个元素的表 S 中的第 k 个最小的元素。

基本的算法是简单的递归策略。设 N 大于截止点(cutoff point)，在截止点后元素将进行简单的排序，v 是选出的一个元素，叫做枢纽元(pivot)。其余的元素被放在两个集合 和 中。 含有那些不大于 v 的元素，而 则包含那些不小于 v 的元素。

为了得到一个线性算法，必须保证子问题只是原问题的一部分，而不仅仅只是比原问题少几个元素。这里要解决问题就是如何花费更少的时间来寻找枢纽元。

为得到一个好的最坏情形，关键想法是再用一个间接层。不是从随机元素的样本中找出中项，而是从中项的样本中找出中项。

基本的枢纽元选择算法如下：

上面给出的枢纽元选择法，有一个专业的术语，叫做“五分化中项的中项”。“五分化中项的中项”保证每个递归子问题的大小最多是原问题的大约 70%。对于整个选择算法，枢纽元可以足够快的算出，以确保 的运行时间。

定理：使用“五分化中项的中项”的快速选择算法的运行时间为 。

分治算法还可以用来降低算法预计所需要的比较次数。

设有 N 个数的集合 S 并且要寻找其中第 k 个最小的数 X。我们选择 S 的子集 S‘，令 δ 是某个数，使得计算过程所用的平均比较次数最小化。

找出 S’ 中第 ( ) 个和第 个最小的元素，几乎可以肯定 S 中的第 k 个元素将落在 和 之间，此时，问题变成了 2δ 个元素的选择问题。

经过分析，会发现，若 和 ，则期望的比较次数为 ，除低次项外它是最优的。（如果 k>N/2，那么我们可以考虑查找第(N-k)个最大元素的对称问题。）

最后一项代表进行两次选择以确定 和 的代价。假设采用合理聪明的策略，则划分的平均代价等于 N 加上 在 S 中的期望阶(expected rank)，即 。如果第 k 个元素在 S‘ 中出现，那么代价就是 O(N)。然而，s 和 δ 已经被选取以保证这种情况以非常低的概率 o(1/N) 发生，因此该可能性的期望代价是 o(1)，当它的 N 越来越大时趋向于 0。

这个分析指出，找出中项平均大约需要 1.5N 次比较。当然，该算法为计算 s 需要浮点运算，这在一些机器上可能使该算法减慢速度。不过即使是这样，若能正确实现，则该算法完全能够比得上快速选择实现方法。

4. 程序员都应该精通的六种算法，你会了吗

对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。

那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。

一、分治算法

分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治算法一般分为三个部分：分解问题、解决问题、合并解。

分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。

典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下：

def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Math.max(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Math.max(leftMax,rightMax);

二、贪心算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。

典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。

贪心策略就是，每次都先拿性价比高的，判断不超过C。

三、迭代算法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。

迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。

典型例子比如说，用迭代算法计算斐波那契数列。

四、枚举算法

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。

枚举算法适用于候选答案数量一定的情况。

典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下：

五、回溯算法

回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。

六、动态规划算法

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。

典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。