常用算法：分治算法、贪心算法、动态规划、回溯法、分支限界、概率算法、随机算法等。

分治算法

分治算法的主要步骤是：分解、求解、合并。

分治算法常用的实现方法是递归。因为分治就是将大问题不断划分成小问题，递归的解决小问题，再合并小问题的解就可以得到问题的解。

递归

递归，就是在函数内部调用本函数自身。形式如下

void foo()

{
         //...
         foo();   //递归
         //...
}

经典问题

阶乘，Hanoi问题，全排列问题

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

动态规划

分治算法将规模较大的问题划分成规模较小的子问题，通常，这些子问题是不重叠的。

而动态规划算法，也是基于问题划分，区别在于划分的子问题是有重叠的，这样在求解的过程中，对于重叠的部分只要求解一次，记录下结果（备忘录方法），其他子问题中直接使用即可，减少了重复计算，效率更高。

动态规划算法常用于求解最优解问题。

动态规划算法

所谓动态规划，其动态就表现在求解一个问题最优解时，不是固定的计算、合并某些子问题的解，而是根据各子问题的解的情况，选择其中最优的。

例如：DP(n) = max{ DP(n-1)+1, DP(n-2)+2 }

求解规模为n的问题的解，等于DP(n-1)+1 和 DP(n-2)+1中的较大的值。

动态规划的要素

显然，不是所有问题都能（或需要）使用动态规划算法求解。一个问题如果需要用动态规划算法求解，它需要具有如下两个性质（要素）：

1）最优子结构性质

问题的最优解包含了其子问题的最优解，这种性质称为最优子结构性质。

该性质是指问题的最优解，是由其子问题的最优解构成，但具体是怎么构成的？不是简单的自下而上，诸如由DP(n-1)的最优解得到DP(n)的最优解之类，而是DP(n)的最优解可能由DP(n-1)构成，也可能和DP(n-1)没有关系，而是由DP(n-2)的最优解构成。这就是定义里用的是包含的意思。

2）子问题重叠性质

动态规划算法其实是一种自下而上的算法，先计算出子问题的解，再由子问题的解去构造问题的解。

由于子问题存在有重叠，所以可以通过备忘录的方法，把子问题的最优解记录下来，当再次用到时，直接从备忘录中读取即可，不必再次使用，这就提高效率。

动态规划的步骤

包括如下4个步骤：

描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由最优解的值构造一个最优解

最优解的值指的是：求解得到的问题的最优的值，如最大值，最小值；

最优解指的是：得到最优的值时所用的具体方法，如背包问题中具体怎么放置物品；

经典问题

（1）装配线调度

（2）矩阵连乘

（3）最长公共子序列

（4）背包问题

（5）多边形游戏

（6）最优三角剖分

（7）最优排序二叉树

（8）最优合并问题

贪心算法

贪心算法中“贪心”二字形象的说明了该算法的基本思想：贪心（每一步选择都是眼下的局部最优选择）。

贪心算法常用于求解最优解问题，比动态规划思路简单，前提是要求问题满足贪心选择性质。

形象的讲：

贪心算法的每次选择就是只看当前的利益，不管当前的选择对后面选择的影响，所以如果当前的选择对之后的选择有影响时，这种选择就不一定最优了。

动态规划就是三思而后行，在考虑当前选择能产生的各种结果中选择一个最优的，想得多速度也就慢了。

经典问题

（1）背包问题（物体可切分时的0-1背包问题）

（2）Huffman编码

（3）单源最短路径

（4）Prim算法

（5）Kruskal算法

（6）最优三角剖分

回溯算法

把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

基本思想类同于：

图的深度优先搜索

二叉树的后序遍历

分支限界法

把问题的解空间转化成了图或者树的结构表示，然后使用广度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

思想类同于：

图的广度优先遍历
二叉树的层序遍历

回溯法的详细描述：回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：

使用约束函数，剪去不满足约束条件的路径；
使用限界函数，剪去不能得到最优解的路径。

当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。

回溯法的实现方法有两种：递归和递推（也称迭代）。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。（类比于图深度遍历的递归实现和非递归（递推）实现）。1. 递归：思路简单，设计容易，但效率低。2. 算法设计相对复杂，但效率高。

1) 子集树

所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间成为子集树。

如0-1背包问题，从所给重量、价值不同的物品中挑选几个物品放入背包，使得在满足背包不超重的情况下，背包内物品价值最大。它的解空间就是一个典型的子集树。

回溯搜索子集树的范式如下：

void backtrack (int t)
{
  if (t>n) output(x);
    else
      for (int i=0;i<=1;i++) {
        x[t]=i;
        if (constraint(t)&&bound(t)) backtrack(t+1);
      }
}

2) 排列树

所给的问题是确定n个元素满足某种性质的排列时，相应的解空间就是排列树。

如旅行售货员问题，一个售货员把几个城市旅行一遍，要求走的路程最小。它的解就是几个城市的排列，解空间就是排列树。回溯搜索排列树的算法范式如下：

void backtrack (int t)
{
  if (t>n) output(x);
    else
      for (int i=t;i<=n;i++) {
        swap(x[t], x[i]);
        if (constraint(t)&&bound(t)) backtrack(t+1);
        swap(x[t], x[i]);
      }
}

*经典问题 *
（1）装载问题

（2）0-1背包问题

（3）旅行售货员问题

（4）八皇后问题

（5）迷宫问题

（6）图的m着色问题