NOIP初赛复习14基本算法思想 一个程序往往要包含两个方面的描述：一是对数据组织的描述，就是数据的类型和数据的组织形式（例如数组），称作数据结构；
一是对程序操作流程的描述，就是程序的操作步骤，也就是所谓算法。正如著名的计算机科学家沃思（Nikiklaus Wirth）提出的公式：数据结构+算法=程序。

算法，广义地讲就是解决问题的方法和过程。可以使用自然语言、伪代码、流程图等多种不同的方法来描述。如果把一个程序比喻成一个具有生命的人，那么数据结构就是这个人的躯体，而算法则是这个人的灵魂。

枚举 枚举法，又称穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。

基本思想：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。总的来说，枚举就是通过列举所有的可能性进行一一判断检查。

适用条件：
1、可预先确定每个状态的元素个数n。

2、可预先确定每个状态元素a1,a2,…,an的值域。

注意事项：使用枚举思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。这里有两点需要注意。一是解空间的划定必须保证覆盖问题的全部解。如果解空间集合用H表示，问题的解集用h表示，那么只有当时，才能使用枚举法求解。二是解空间集合及问题的解集一定是离散的集合，也就是说集合中的元素是可列的、有限的。

常见类型：枚举排列、枚举子集。

常见方法： 递归地枚举，这种方法往往更为直观；
递推（循环）地枚举，这种方法往往写起来更为简洁。

主要优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。

主要缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。在某些情况下，我们可以通过利用题目的特点去除相当大的一部分情况的列举，从而提高枚举的效率。

算法优化：
1、    提取有效信息; 2、    减少重复计算; 3、    将原问题化为更小的问题; 4、    根据问题的性质进行截枝; 5、    引进其他算法。

例：NOIP2016玩具谜题、NOIP2014生活大爆炸版石头剪刀布等 递推 递推是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。

基本思想：递推是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

主要步骤：建立递推关系式；
确定边界条件；
递推求解。

应用分类：一般递推问题；
组合计数类问题；
一类博弈问题的求解；
动态规划问题的递推关系。

动态规划与递推的关系 1、一般递推边界条件很明显，动态规划边界条件比较隐蔽，容易被忽视；

2、一般递推数学性较强，动态规划数学性相对较弱；

3、一般递推不划分阶段，动态规划一般有较为明显的阶段。

五种典型的递推关系 1、Fibonacci数列 在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。

问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则：
Fx=Nx+Fx-1 Nx=Fx-2  (即第x-2个月的所有兔子到第x个月都有繁殖能力了) ∴Fx=Fx-1+Fx-2  边界条件：F0=0，F1=1 由上面的递推关系可依次得到 F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。

Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到了较好的体现。

2、Hanoi塔问题 问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。

要求把a柱上n个圆盘按下述规则移到c柱上：
1、一次只能移一个圆盘；

2、圆盘只能在三个柱上存放；

3、在移动过程中，不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ 解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；
然后将大盘子从a柱移到c 柱；
最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；
再借助a柱把b柱上的n-1个盘子移动到c柱上；
总共移动hn-1+1+hn-1个盘次。

∴hn=2hn-1+1    边界条件：h1=1 3、平面分割问题 问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

解：设an为n条封闭曲线把平面分割成的区域个数。

由图3-13可以看出：a2-a1=2；
a3-a2=4；
a4-a3=6。

从这些式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1。

4、Catalan数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。

问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为Catalan数。例如五边形有如下五种拆分方案，故h5=5。求对于一个任意的凸n边形相应的hn。

NOIP初赛复习（三）栈与卡特兰数>>> Catalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。

5、第二类Stirling数 在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。

定义：n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。

下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。

解：设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：
1、bn独自占一个盒子；
那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；

2、bn与别的球共占一个盒子；
那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。

综合以上两种情况，可以得出第二类Stirling数定理：
S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)   (n>1,m1) 边界条件可以由定义2推导出：
S2(n,0)=0；
S2(n,1)=1；
S2(n,n)=1；
S2(n,k)=0(k>n)。      小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。

递归 一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。

基本思想：
1、递归是借助于一个递归工作栈来实现。递归=递推+回归。

2、递推：问题向一极推进, 这一过程叫做递推。这一过程相当于压栈。

3、回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。

注意事项：
1、    递归就是在过程或函数里调用自身；

2、    在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

主要优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。

主要缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。

应用分类：
1、递归的定义问题。树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。

2、解决搜索问题。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。

3、实现分治思想。不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。

4、用于输出动态规划的中间过程。动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。

【例】 给定n（n>=1）,用递归的方法计算1+2+3+4+...+(n-1)+n。

算法分析：本题可以用递归方法求解，其原因在于它符合递归的三个条件：
1、本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n; 2、给定n,所以是有限次的递归调用；

3、结束条件是当n=1，则s=1。

【参考程序】 #include<iostream> using namespace std; int fac(int);                    //递归函数 int main() { 　　int t; 　　cin>>t;                   //输入t的值 　　cout<<“s=“<<fac(t)<<endl;          //计算1到t的累加和，输出结果 } int fac(int n) { 　　if (n==1) return 1; 　　return (fac(n-1)+n);          //调用下一层递归 } 运行程序，当T=5时，输出结果：S=15，其递归调用执行过程如下图：（设T=3） 递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法——栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。

递归 递推 适合解决的问题 1. 问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的 2. 需要利用分治思想解决的问题 3. 回溯、深度优先搜索 4. 输出动态规划的中间过程 1. 能够用递推式计算的数学题 2. 动态规划（必须使用递推或记忆化搜索） 特点 结构清晰、可读性强 目的性强 速度较快、比较灵活 思路不易想到 编码方式 在函数中调用自己 迭代（使用for循环等） 替代方法 问题的性质不同，改写的方法也不同。

① 有的问题可以根据程序本身的特点，使用栈来模拟递归调用。

② 有的问题可以改写成递推或迭代算法。

在拓扑关系不明显时，可以采用记忆化搜索。

搜索 搜索，某种意义上就是对于枚举算法的一种改进，通过在枚举的过程中，不断排除一些不可能达到的情况，从而达到优化复杂度的效果。

常见方法：
1、深度优先搜索（DFS） 主要思想：从一个顶点沿一条路一直走，如果发现到不了目标节点，则返回上一个节点，沿另一条路一直走到底。总体来说，DFS就是一个一个一直处理到底，发现无法得到结果之后，逐步返回寻求其它的出路。

算法优化：
1、最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝；

2、可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出；

3、记忆化搜索：对于已经搜索过的状态直接退出；

4、改变搜索顺序：对于看起来希望更大的决策先进行搜索；

5、优化搜索策略；

6、预处理找到大体搜索翻译；

7、改写成IDA*算法。

2、宽度优先搜索（BFS） 主要思想：首先访问起始节点的所有邻接点，然后再访问较远的区域，逐步扩大范围，直到找到了目标节点。BFS是一个处理不含边权的图当中求解最短路径的一个非常有效的方法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

注意事项：
1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲。

2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间和空间，还有可能陷入死循环。

3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用宽度优先搜索；
如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。

4、宽度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。

算法优化：
1、判重的优化：hash，二叉排序树；

2、双向广搜或启发式搜索；

3、改写成A*算法；

4、二分优化。

DFS BFS 优势 1. 比较适合回溯类搜索 2. 参数传递、状态修改和恢复都比较方便 3. 自顶向下地处理问题 4. 记忆化搜索容易实现 5. 能很快到达解答树的底端 1. 解决“最少步数”、“深度最小”问题 2. 问题的解靠近解答树的根结点 3. 启发式搜索在BFS中更容易实现 4. 能立刻停止搜索 缺点 1. 使用递归算法容易导致栈溢出 2. 有时不容易输出方案 3. 不易立即结束搜索 1. 空间一般比DFS大 2. 状态重复的排除有时耗时多 3、迭代加深搜索 深度优先搜索的优点在于能较高效地逼近解，缺点在于初始递归方向错误会带来很严重后果；
宽度优先搜索的优点在于能迅速找到答案不算大的解，缺点在于解答案较大时所耗时间与空间都比较大。于是，在综合以上两个算法之后，出现了一个折中的方法：迭代加深搜索。

主要思想：通过限定下界k，然后允许深度优先搜索搜索k层，一旦仍没有找到有效解，则增大下界。

主要优点：相对于深度优先搜索并没有大很多的时间开销，但能部分解决深度优先搜索的局限；
无需宽度优先搜索一般的大空间需求。

【例】迷宫问题 如下图所示，给出一个N*M的迷宫图和一个入口、一个出口。

编一个程序，打印一条从迷宫入口到出口的路径。这里黑色方块的单元表示走不通（用-1表示），白色方块的单元表示可以走（用0表示）。只能往上、下、左、右四个方向走。如果无路则输出“no way.”。

入口 → 0 -1 0 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 0 0 -1 -1 -1 0 0 -1 -1 0 0 0 0 0 → 出口 0 0 0 0 0 0 0 -1 -1 算法分析：只要输出一条路径即可，所以是一个经典的回溯算法问题，本例给出了回溯（深搜）程序和宽搜程序。

【深搜参考程序】 #include <iostream> using namespace std; intn,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51]; bool f; int move(int x, int y,int step) {  map[x][y]=step;     //走一步，作标记，把步数记下来  a[step]=x;  b[step]=y;             //记路径   if((x==desx)&&(y==desy))   {    f=1;   totstep=step;   }    else    {      if((y!=m)&&(map[x][y+1]==0)) move(x,y+1,step+1);         //向右      if((!f)&&(x!=n)&&(map[x+1][y]==0))  move(x+1,y,step+1);   //往下      if((!f)&&(y!=1)&&(map[x][y-1]==0))  move(x,y-1,step+1);   //往左      if((!f)&&(x!=1)&&(map[x-1][y]==0))  move(x-1,y,step+1);   //往上    } } int main() {   int i,j;  cin>>n>>m;                     //n行m列的迷宫   for(i=1;i<=n;i++)   //读入迷宫，0表示通，-1表示不通    for (j=1;j<=m;j++)    cin>>map[i][j];   cout<<“input the enter:“;  cin>>soux>>souy;               //入口  cout<<“input the exit:“;  cin>>desx>>desy;               //出口   f=0;      //f=0表示无解；
f=1表示找到了一个解  move(soux,souy,1);   if (f)   {     for(i=1;i<=totstep;i++)              //输出直迷宫的路径     cout<<a[i]<<“,“<<b[i]<<endl;   } else cout<<“no way.“<<endl; return 0; } 【宽搜参考程序】 #include <iostream> using namespace std; int u[5]={0,0,1,0,-1},    w[5]={0,1,0,-1,0}; intn,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51]; bool f; int print(int d) {   if (pre[d]!=0)print (pre[d]);             //递归输出路径  cout<<a[d]<<“,“<<b[d]<<endl; } int main() {   int i,j;  cin>>n>>m;                        //n行m列的迷宫   for(i=1;i<=n;i++)   //读入迷宫，0表示通，-1表示不通    for (j=1;j<=m;j++)     cin>>map[i][j];   cout<<“input the enter:“;  cin>>soux>>souy;                             //入口  cout<<“input the exit:“;  cin>>desx>>desy;                             //出口   head=0;   tail=1;   f=0;  map[soux][souy]=-1;  a[tail]=soux;  b[tail]=souy;pre[tail]=0;   while(head!=tail)                           //队列不为空   {    head++;     for(i=1;i<=4;i++)                        //4个方向     {      x=a[head]+u[i];  y=b[head]+w[i];       if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(map[x][y]==0))      {                                     //本方向上可以走         tail++;        a[tail]=x;  b[tail]=y;  pre[tail]=head;        map[x][y]=-1;        if ((x==desx)&&(y==desy))           //扩展出的结点为目标结点         {          f=1;          print(tail);          break;         }       }     }     if(f) break;   }   if (!f)cout<<“no way.“<<endl;   return 0; }   输入1：
输出1：
输入2：
输出2：
8   5 -1   -1 -1  -1 -1  0   0  0  0  -1 -1   -1 -1  0  -1 -1   0  0  0  -1 -1   0  0  -1 -1 -1   0  0  0  -1 -1   -1 -1  0  -1 -1   0  0  0  -1 2 1 8 4 2,1 2,2 2,3 2,4 3,4 4,4 4,3 5,3 6,3 8 5 -1   -1 -1 -1 -1  0   0  0  0 -1 -1   -1 -1  0 -1 -1   0  0  0 -1 -1   0  0 -1 -1 -1   0  0  0 -1 -1   -1 -1 -1 -1 -1   0  0  0 -1 2 1 8 4 no way. 分治 基本思想：将一个较大规模的问题分成多个（一般是2个）较小规模的互相独立且与原问题相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。

适用条件：
1、该问题的规模缩小到一定的程度就可以容易地解决；

2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

3、利用该问题分解出的子问题的解可以合并为该问题的解；

4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

递归与分治的算法思想往往是相伴而生的，它们在各类算法中使用非常频繁，应用递归和分治的算法思想有时可以设计出代码简洁且比较高效的算法来。

解题步骤：
1、分解，将要解决的问题划分成若干规模较小的同类问题；

2、求解，当子问题划分得足够小时，用较简单的方法解决；

3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

应用分类： 二分搜索；
大整数乘法；
Strassen矩阵乘法；
棋盘覆盖；
合并排序；
快速排序；
线性时间选择；
最接近点对问题；
循环赛日程表；
汉诺塔等。

例：NOIP2012借教室；
NOIP2013转圈游戏等 【例】用递归算法实现二分查找即：有n个已经从小到大排序好的数据，输入一个数m，用二分查找算法，判断它是否在这n个数中。

#include<iostream> using namespace std; int jc(int,int); int n,a[1000],m; int main() {   intx,y,i;   cin>>n;   x=1;y=n;   for(i=1;i<=n;i++)                       //输入排序好的数   cin>>a[i];  cin>>m;                                //输入要查找的数  jc(x,y);                                 //递归过程  cout<<endl;    } int jc(int x,int y)                           //递归过程 {    int k;   k=(x+y)/2;                          //取中间位置点    if(a[k]==m)    cout<<“thennum in  “<<k<<endl;        //找到查找的数，输出结果    if (x>y)cout<<“no find“<<endl;         //找不到该数            else              {                if (a[k]<m) jc(k+1,y);         //在后半中查找                if (a[k]>m) jc(x,k-1);         //在前半中查找              } } 贪心 基本思想：贪心，又称贪婪算法。指的是在对问题求解过程中，总是做出目前来看最优的选择，也就是说贪心算法不会考虑全局最优解，而只会不断考虑局部最优解。是一种对某些求最优解问题的更简单、更迅速的设计技术。往往可以以较低的代码复杂度与时间复杂度而得到较优的结果，对于求解近似值的作用很大。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

当存在一些题目的正解想不出来，并且一个贪心原则又效果不好的情况下，可以采取多个贪心原则同时用，并取最优的方案来解决。但对于相当一部分需要求解最优值的问题，实际上我们会发现我们通常可以采用动态规划或者网络流的方法取代贪心算法。

适用条件：
1、可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

2、原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在下面示例的背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。

3、其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。

解题步骤：
1、建立数学模型来描述问题；

2、把求解的问题分成若干个子问题；

3、对每一子问题求解，得到子问题的局部最优解；

4、把子问题的解局部最优解合成原来解问题的一个解。

例：NOIP2012国王游戏；
NOIP2013积木大赛；
NOIP2015跳石头等。

【例】部分背包问题 给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

算法分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答，方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。

因此我们非常容易设计出如下算法：
问题初始化；

                            //读入数据 按Vi从大到小将商品排序；

　　i=1; 　　do 　　{  　　  if (m==0)  break;       //如果卡车满载则跳出循环 　　  m=m-w[i]; 　　  if (m>=0)                    //将第i种商品全部装入卡车 　　  else  将(m+w[i])  重量的物品i装入卡车; 　　  i=i+1;                                 //选择下一种商品 　　}while (m>0&&i<=n); 在解决上述问题的过程中，首先根据题设条件，找到了贪心选择标准(Vi)，并依据这个标准直接逐步去求最优解，这种解题策略被称为贪心法。

 回溯 基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；
如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。

【例】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

算法分析：非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；
与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

算法流程：
1、数据初始化；
   2、递归填数：判断第i个数填入是否合法 A、如果合法：填数；
判断是否到达目标（20个已填完）：是，打印结果；
不是，递归填下一个；

B、如果不合法：选择下一种可能。

【参考程序】 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> using namespace std; bool b[21]={0}; int total=0,a[21]={0}; int search(int);                    //回溯过程 int print();                       //输出方案 bool pd(int,int);                  //判断素数 int main() {     search(1);    cout<<total<<endl;         //输出总方案数 } int search(int t) {     int i;     for(i=1;i<=20;i++)          //有20个数可选      if(pd(a[t-1],i)&&(!b[i]))        //判断与前一个数是否构成素数及该数是否可用       {         a[t]=i;         b[i]=1;          if(t==20) { if (pd(a[20],a[1])) print();}             else search(t+1);         b[i]=0;       } } int print() {    total++;   cout<<“<“<<total<<“>“;    for (intj=1;j<=20;j++)     cout<<a[j]<<“ “;   cout<<endl;   } bool pd(int x,int y) {     intk=2,i=x+y;     while(k<=sqrt(i)&&i%k!=0) k++;     if(k>sqrt(i)) return 1;        elsereturn 0; } 动态规划 基本思想：在多阶段决策的问题中，各个阶段采取的决策，一般来说是与时间或空间有关的。决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。

基本概念：
阶段：把所求问题的过程按照时间或空间恰当地分成若干个相互联系的阶段。

状态：表示每个阶段的客观状态，它既是某阶段的出发位置，又是前一阶段的终点。

无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所以各阶段确定时，整个过程也就确定了。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段状态的一种选择(行动)。

策略：由每个阶段的决策组成的序列。

最优性原理：把一个大问题划分成多个子问题，对于整个问题必须最优的情况时，问题也必须最优，即问题具备最优子结构的性质。

适用条件：
1、最优子结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。

2、重叠子问题。在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题 ……。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。

3、无后效性原则。已经求得的状态，不受未求状态的影响。

解题步骤：
1、判断问题是否具有最优子结构性质，若不具备，则不能用动态规划；

2、把问题分成若干个子问题(分阶段)；

3、建立状态转移方程(递推公式)；

4、找出边界条件；

5、设定初始值；

6、递推求解。

状态转移方程的构造是动态规划过程中最重要的一步，也是最难的一步。对于大多数的动态规划，寻找状态转移方程有一条十分高效的通道，就是寻找变化中的不变量（已经求得的值）。

例：背包型动态规划：POJ1014,1068；
序列型动态规划：POJ 1044,1576,3027；
区间型动态规划：POJ 1048,1154,1166；
棋盘性动态规划：POJ 1010,1169,1219,1220；
划分型动态规划：POJ 1017,1039,1040；
树型动态规划：POJ 1163,1380等 【例1】最短路径问题 下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？ 算法分析：把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；
第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用DK（XI，X+1J）表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离，FK（XI）表示从第K阶段的XI到终点E的最短距离，利用倒推的方法，求解A到E的最短距离。

具体计算过程如下：
S1：
K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3；

S2：
K = 3 有 F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）}         = MIN{ 5+3，6+4 } = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6 S3：
K = 2 有   F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9 F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）}         = MIN{ 8+8，4+6 } = 10 S4：
K = 1 有 F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）}        = MIN{ 5+9，3+10} = 13 因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；
最短路程长度为13。

从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。

#include<iostream> #include<cstring> usingnamespace std; intmain() {    long d[5][5][5],f[10][10];   memset(d,42,sizeof(d));          //有些路径是不通的,赋值为较大值，用于判断    d[1][1][1]=5;d[1][1][2]=3;d[2][1][1]=1;   //以下给可通路径赋正常值    d[2][1][2]=6;d[2][1][3]=3;d[2][2][2]=8    d[2][2][4]=4;d[3][1][1]=5;d[3][1][2]=6;    d[3][2][1]=5;d[3][3][3]=8;d[3][4][3]=3;    d[4][1][1]=3;d[4][2][1]=4;d[4][3][1]=3;    for (int i=0;i<=9;++i)     for (int j=0;j<=9;++j) f[i][j]=10000000;    f[5][1]=0;    for (int i=4;i>=1;--i)     for (int j=1;j<=4;++j)      for (int k=1;k<=4;++k)        if(f[i][j]>d[i][j][k]+f[i+1][k])     //即使走非法路径，也不影响答案           f[i][j]=d[i][j][k]+f[i+1][k];     cout<<f[1][1]<<endl; } 【例2】混合背包 一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

【输入格式】 第一行：二个整数，V(背包容量，V<=200)，N(物品数量，N<=30)；

第2..N+1行：每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi)。

【输出格式】 仅一行，一个数，表示最大总价值。

【样例输入】mix.in 104 2  1  0 3  3  1 4  5  4 【样例输出】mix.out 11 【样例解释】 选第一件物品1件和第三件物品2件。

【参考程序】 #include<cstdio> using namespace std; int m, n; int w[31], c[31], p[31]; int f[201]; int max(int x,int y) { return  x>y?x:y; } int main(){    scanf(“%d%d“,&m,&n);     for (int i =1; i <= n; i++)        scanf(“%d%d%d“,&w[i],&c[i],&p[i]);     for (int i =1; i <= n; i++)         if (p[i]== 0)  {                        //完全背包             for(int j = w[i]; j <= m; j++)                f[j] = max(f[j], f[j-w[i]]+c[i]);         }         else {             for(int j = 1; j <= p[i]; j++)  //01背包和多重背包                for (int k = m; k >= w[i]; k--)                    f[k] = max(f[k],f[k-w[i]]+c[i]);         }    printf(“%d“,f[m]);     return 0; } 按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。