NOIP从递归深搜到动态规划(C++)

从递归深搜到动态规划提纲一、函数及其递归调用二、深度优先搜索三、动态规划一、函数及其递归调用一个C++程序无论大小都是由一个或多个“函数”组成。其中必须有且只有一个main()函数，称之为“主函数”，由main()调用其它函数来完成程序的特定功能。当然，其它函数之间也可以按照规则互相调用。C++中的函数由一段相对独立的代码组成，这段代码能实现某一项具体、独立、完整的功能。函数在程序设计中的作用主要有两个，一是“代码重用”，二是“问题分解”。一、函数及其递归调用定义函数的格式如下：返回值类型函数名（参数列表）{

函数体}函数调用是通过“函数名”进行的，一般格式为：函数名（参数列表）一、函数及其递归调用函数调用方式有以下三种：（1）函数调用作为一条独立语句，完成一件事情，没有任何返回值。例如：print(n)；doit(dep,total)；（2）函数调用的结果作为表达式的一部分。例如：intt=compute(i,j)+i*j；（3）以实参形式出现在其它函数调用中。例如：number=min(sum(-5,100),n)；num=max(max(a,b),c)。一、函数及其递归调用例1、最大公约数【问题描述】输入两个正整数m和n，求它们的最大公约数。【输入格式】一行两个正整数m和n，用一个空格隔开，2≤m，n≤10000。【输出格式】一行一个整数，表示m和n的最大公约数。【输入样例】2436【输出样例】12一、函数及其递归调用演示：欧几里德“辗转相除法”

，体会其中的递归思想。一、函数及其递归调用例2、分解质因子【问题描述】输入一个正整数n，用递归方法从小到大输出它的所有质因子（因子是质数）。【输入格式】一行一个整数n，2≤n≤10000。【输出格式】一行若干个整数，两数之间用一个空格隔开，从小到大输出。【输入样例】18【输出样例】233一、函数及其递归调用如果n等于1，就没法再分解了。如果n大于1，从整数p（p从2开始）开始试除。如果n能被p整除，就得到一个质因子p。问题就转化成对于整数n/p，从p开始继续分解质因子。如果n不能被p整除，问题就转化为对于整数n，从p+1开始分解质因子。所以，递归公式为：一、函数及其递归调用一、函数及其递归调用递归的原理（操作系统的内部实现机制）例3、汉诺塔一、函数及其递归调用

定义函数：move(n,A,B,C)，将n只盘子从A柱经B柱搬到C柱，分解为3步：1、move(n-1,A,C,B)：将上面的n-1只盘子作为一个整体从A柱经C柱移至B柱；2、输出n：AtoC：将n号盘从A柱移至C柱，是直接可操作的；3、move(n-1,B,A,C)：将上面的n-1只盘子作为一个整体从B柱经A柱移至C柱；

这显然是一种递归定义，当求解move(n-1,A,C,B)时，又要将其分解为3步：1.1、将上面n-2只盘子作为一个整体，从A经B移到C，即：move(n-2,A,B,C)；1.2、第n-1号盘子从A直接移至B，即n-1：AtoB；1.3、再将上面n-2只盘子作为一个整体，从C经A移到B，即：move(n-2,C,A,B)；一、函数及其递归调用voidmov(intn,chara,charb,charc){ if(n==1)cout<<a<<"->"<<c<<endl;//递归边界 else{ mov(n-1,a,c,b); cout<<a<<"->"<<c<<endl; mov(n-1,b,a,c); }}

mov(n,'A','B','C');

演示：调用执行过程，分析递归原理（操作系统的内部实现机制）。二、深度优先搜索BFS&DFS二、深度优先搜索例如，无向图的深度优先遍历：从顶点V0开始进行深度优先搜索，得到的一个序列为：V0，V1，V2，V6，V5，V3，V4V0,V2,V6,V1,V4,V3,V5V0,V2,V1,V4,V6,V5,V3V0,V2,V4,V1,V6,V5,V3V2,V4,V1,V6,V5,V3,V0二、深度优先搜索深度优先搜索（DepthFirstSearch，简写DFS），简称深搜，其状态“退回一步”的顺序符合“后进先出”的特点，符合“栈”的思想。深搜的空间复杂度较小，因为它只存储了从初始状态到当前状态的一条搜索路径。但是，深搜找到的第一个解不一定是最优解，要找最优解必须搜索整棵“搜索树”。所以，深搜适用于要求所有解方案的题目。深搜的特点：递归调用，简单易写。写清终止条件以及调用方式，其他就交给系统吧。不过，系统栈的大小有限制，容易崩溃。因此，有时需要非递归的手工栈。二、深度优先搜索DFS算法框架（直接递归）

voiddfs(intdep，参数表){

自定义参数；

if(当前是目标状态){

输出解或者作计数、评价处理;

}else

for(i=1;i<=状态的拓展可能数;i++)

if(第i种状态拓展可行){

维护自定义参数;

dfs(dep+1,参数表);

}}二、深度优先搜索例4、体积【问题描述】

给你n件物品，每件物品有一个体积Vi，求从中取出若干件物品能够组成的不同的体积和有多少种可能。例如，n=3，Vi=（1，3，4），那么输出6，6种不同体积和具体为1、3、4、5、7、8。【输入格式】第一行1个整数，表示n；第二行n个整数，表示Vi，每两个数之间用一个空格隔开。【输出格式】一行一个数，表示不同的体积和有多少种可能。二、深度优先搜索【输入样例】3134【输出样例】6【数据规模】对于30%的数据满足：n≤5，Vi≤10；对于60%的数据满足：n≤10，Vi≤20；对于100%的数据满足：n≤20，1≤Vi≤50。二、深度优先搜索【问题分析】

对于每一件物品只有取和不取两种情况，假设V表示目前方案的体积和，初始化为0。设计一个哈希表hash[i]，表示体积i是否出现过，初始化为false。先考虑取第一件物品，等到这个情况处理完，再退回到这一步处理不取第一件物品。所以，对于样例来说，这个时候V=1；然后再递归处理第二件物品，同样先处理取的情况，处理完再回来处理不取的情况，所以，此时V=4；再递归处理第三件物品，同样先处理取的情况，此时V=8，三件物品已经处理完毕，得到一个体积8，hash[8]=true。再考虑不取第三件物品的情况，此时得到一个体积4，hash[4]=true。处理完第三件物品的两种状态，退回到上一步处理第二件物品不取的情况，此时体积V=1。再往前递归一步，考虑第三件物品的取与不取，此时分别得到2个体积和V=5和V=1，hash[5]=true，hash[1]=true。再连续退回二次，回到第一件物品不取的情况，分别处理，…最后，统计hash[i]为true的个数。二、深度优先搜索

以上深度优先搜索的算法思想，本质上就是有序穷举出2^n种可能，去掉重复的体积和，一种方案本质上对应着一个二进制数，如图所示，一个结点的左分支代表取当前物品、右分支代表不取当前物品。

二、深度优先搜索二、深度优先搜索例5、最大黑区域黑白位图是由黑白两种像素点组成的矩形点阵，图像识别的一个操作是求出黑白位图中最大黑区域的面积。请你设计一个程序完成这个任务。黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像素相邻（仅指上、下、左、右相邻）。两个不同的黑区域没有相邻的像素点。一个黑区域的面积是其所包含的像素点的个数。输入：第一行含两个整数n和m(1<=n,m<=100),分别表示图像的行数与列数；后面紧跟着n行，每行含m个整数0或1，其中第i行表示图像的第i行的m个像素，0表示白像素，1表示黑像素。每一行的2个数之间有一个空格分隔。输出：相应的图像中最大黑区域的面积。二、深度优先搜索样例输入：56011001110101010010000111101110样例输出：7算法分析

从左上角开始，找到一个黑点(a[i,j]=1)，然后dfs(i,j)，dfs到的点置为0，一次dfs完毕得到一个返回值max，就是这个黑区域的面积。

主程序中通过打擂台记录最大的max给ans，再找（穷举）下一个黑点继续dfs。二、深度优先搜索样例输入：56011001110101010010000111101110样例输出：7二、深度优先搜索例6、图的遍历【问题描述】读入一个用邻接矩阵存储的无向图，输出它的深度优先遍历序列。【输入格式】第一行为n，表示图的顶点个数，n≤20；以下为n*n的邻接矩阵，a[i,j]=0表示顶点i与顶点j不存在边，a[i,j]=1表示顶点i与顶点之间有边连接。【输出格式】从顶点开始的深度优先搜索序列，具体格式参加输出样例。【输入样例】80110000010011000100000110100010001000100000110000010000100100010【输出样例】1-2-4-6-5-3-7-8二、深度优先搜索二、深度优先搜索搜索的优化方法之一：剪枝在深度优先搜索的过程中，如果发现当前状态往下搜索，不可能得到解或者最优解，那么就应该及时“后退”，避免搜索当前结点（状态）下面的“子搜索树”，以减少搜索时间，提高搜索效率，这种思想称为搜索“剪枝”。这就跟走迷宫时提前判断出“死胡同”，不走冤枉路一个意思。剪枝分为：可行性剪枝和最优化剪枝二、深度优先搜索例7、门票问题【问题描述】有很多人在门口排队，每个人将会被发到一个有效的通行密码作为门票。一个有效的密码由L(3≤L≤15)个小写英文字母组成，至少有一个元音('a','e','i','o'或'u')和两个辅音(除去元音以外的音节)，并且是按字母表顺序出现的(例如，'abc'是有效的，而'bac'不是)。现在给定一个期望长度L和C（1≤C≤26）个小写字母，写一个程序，输出所有的长度为L、能由这给定的C个字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。【输入格式】第1行:两个由一个空格分开的整数，L和C，3≤L≤15，1≤C≤26；第2行:C个由一个空格隔开的小写字母，密码是由这个字母集中的字母来构建的。【输出格式】若干行，每行输出一个长度为L个字符的密码(没有空格)。输出行必须按照字母顺序排列。你的程序只需输出前25000个有效密码，即使后面还存在有效密码。二、深度优先搜索【输入样例】46atcisw【输出样例】acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw二、深度优先搜索三、动态规划例8、数字三角形（codevs1220）下图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。每个数的范围[0..100]。行数不超过100。三、动态规划样例输入：5738810274445265样例输出：30三、动态规划一个常见的“深搜”式写法：inta[101][101]，ans=-2147483647;voiddfs(intx,inty,intsum){//表示从上往下，搜索到第x行、第y列得到的最大和sum

sum+=a[x][y];if(x==n){ ans=max(ans,sum);//max函数实现打擂台 return;

}

dfs(x+1,y,sum);//递归到正下方

dfs(x+1,y+1,sum);//递归到右下}主程序中调用dfs(1,1,0)，输出ans即可。三、动态规划一个“描述问题”式的深搜写法：intopt(intx,inty){//直接递归求解，由下至上直到a[1][1] if(x==n)returna[x][y]; elsereturna[x][y]+max(opt(x+1,y),opt(x+1,y+1));}答案为?opt(1,1)离动态规划已经非常接近了！三、动态规划两个非常重要的概念：opt(x,y)是问题的描述（状态）opt(x,y)=a[x][y]+max(opt(x+1,y),opt(x+1,y+1))是问题之间的逻辑关系（状态转移方程）但是，以上代码效率低下，为什么？每个节点opt（x,y）会被调用2次，最多被调用2^n次。冗余：重复计算同一个子问题。简单修改一下，就可以得到下面一个高效的写法。三、动态规划一个被称为“记忆化搜索”的版本：intf[101][101];memset(f,-1,sizeof(f));intopt(intx,inty){ if(f[x][y]!=-1)returnf[x][y];//记忆数组，以空间换时间 elseif(x==n)returna[x][y];//直接查表，不再冗余计算 else{

f[x][y]=a[x][y]+max(opt(x+1,y),opt(x+1,y+1));//记忆

returnf[x][y]; }}体现了动态规划非常重要的思想：减少冗余计算。有观点认为：记忆化搜索=动态规划。三、动态规划更加“动态规划”式的写法：intf[101][101];voiddoit(){

for(inti=n;i>=1;i--)//由下往上，阶段性

for(intj=1;j<=i;j++)//求当前阶段每个状态的最优值

if(i==n)f[i][j]=a[i][j];//边界

elsef[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);//根据状态转移方程求值}答案为?f[1][1]三、动态规划如果需要打印具体的选择方案呢？intf[101][101][2];//增加一维，记录最优值的来源voiddoit(){ for(inti=n;i>=1;i--) for(intj=1;j<=i;j++) if(i==n)f[i][j][0]=a[i][j]; elseif(f[i+1][j][0]>=f[i+1][j+1][0]){ f[i][j][0]=a[i][j]+f[i+1][j][0]; f[i][j][1]=0;//由正下方求得 }else{

f[i][j][0]=a[i][j]+f[i+1][j+1][0]; f[i][j][1]=1;//由右下方求得

}}三、动态规划本题小结：搜索与动态规划的相似点：状态、状态转移动态规划的优点：减少冗余计算动态规划的应用场合：求最优解及其具体方案（数）后续学习动态规划的提示：应用动态规划的难点：状态的设计和转移本题：f[i][j]表示从第i行、第j列这个数到最后一行的路径上所有数之和的最大值。那么，状态转移方程为：f[i][j]=a[i][j]+max{f[i+1][j],f[i+1][j+1]}动态规划解题的思维：思考问题采用递归的思想，假设F[1]～F[i-1]已经知道了，如何求F[i]？编程实现采用递推的方法逐步推进。善于画表格，手工求值，体会过程，程序实现就容易了。三、动态规划举一反三：codevs2193上面题目加上一个限制条件：要求路径必须经过第n/2行、第n/2列。思考分析：还是一样的状态表示，假设f[i][j]表示从第i行、第j列这个数到最后一行的路径上所有数之和的最大值。那么，状态转移方程为：

f[i][j]=a[i][j]+max{f[i+1][j],f[i+1][j+1]}只要在编程实现时，当计算到第n/2行时，把所有非f[n/2][

n/2]的状态值都设置为负无穷大。三、动态规划举一反三：codevs2189还是上面的题目，但是要求路径上的所有数之和%100的最大值。思考分析：如果我们还是沿用上面的方法，设计状态、进行状态转移：f[i][j]=(a[i][j]+max{f[i+1][j],f[i+1][j+1]})%100对不对呢？如果不对，你能举出反例吗？按照这个转移，会取(99+3)

%

100

=

2，而实际答案应该是取：

(0+3)%100=3。那么如何修改？三、动态规划思考分析：把%100放到里面去，即：

f[i][j]

=

max{(a[i][j]+f[i+1][j])%100,(a[i][j]+f[i+1][j+1])%100}这样对吗？再给一个例子：按照以上转移，就会取：003这条路径上的数，答案为3。

而如果取：0963这条路径上的数，答案为99。

所以，还是不对。其实，这样定义状态根本就不存在“最优子结构”，也就说：当前（最终）的最优状态不一定由之前得到的最优状态转移而来。三、动态规划那么，本题就不能使用动态规划了吗？其实，还是可以的，我们需要重新设计状态表示和转移方程。设f[i][j][k]表示有没有一条从以第i行、第j个这个数到最后一行的路径上数之和%100=k。f[i][j][k]为布尔型数组。转移方程如下：f[i][j][(k+a[i,j])%100]

=

f[i+1][j][k]||f[i+1][j+1][k]其中：i<n,j<=i,0<=k<100。表示：如果左边或右边有一条%100=k的到最后一行的线路，那么就可以把它转移到这个点的决策。边界条件是f[n][i][a[n,i]%100]为true，1<=i<=n。最后，统计并输出最大的满足

f[i][j][k]为true的k。三、动态规划动态规划算法的思想和概念分治法与动态规划的比较：重叠子问题动态规划对每个子子问题只求解一次，将其结果存在一张表中，从而避免后面每次遇到各个子子问题时重复去计算动态规划通常应用于最优化问题状态状态转移方程适用条件：最优化原理（最优子结构性质）、无后效性分类：线性DP、二维DP、区间DP、树形DP……三、动态规划例9、最长不下降子序列（LIS）题目描述：给一个数组a1,a2...an，找到最长的不下降子序列ab1<=ab2<=...<=abk，其中b1<b2<...<bk。输出最长的不下降子序列长度。样例输入：59

3

6

2

7样例输出：

3样例说明：

367三、动态规划状态的设计：f[i]：表示前i个元素的最长不下降子序列长度？无法描述问题之间的关系！正确的状态表示：前i个元素的最长不下降子序列长度，且第i个元素已经被选。状态的转移：f[i]=max(f[j])+1其中，要满足：a[j]<=a[i]，1<=j<i边界（初始化）：f[i]=1，1<=i<=n意思就是在a[i]之前找一个比a[i]小的a[j]，将a[i]放在以a[j]结尾的LIS序列之后，得到一个新的LIS序列。三、动态规划参考代码：for(inti=1;i<=n;i++){//跟踪样例体会一维DP的求解过程

f[i]=1;//可以把f[i]放在外面初始化为1，然后i从2到n求解

for(intj=1;j<=i-1;j++)

if(a[j]<=a[i])f[i]=max(f[i],f[j]+1);}答案是不是f[n]，为什么？intans=f[1];for(inti=2;i<=n;i++)

if(f[i]>ans)ans=f[i];printf("%d\n",ans);三、动态规划如果要输出方案呢？ for(inti=1;i<=n;i++){

f[i]=1;s[i]=0;

for(intj=1;j<=i-1;j++)

if(a[j]<=a[i])

if(f[j]+1>f[i]){

f[i]=f[j]+1;

s[i]=j;//记录当前的值是由哪个前驱结点求得

} }打擂台输出长度后，再根据这个位置，倒过来找到这个序列是有前面那些元素组成，把这些元素压栈，最后倒序输出栈中的这些数即可。三、动态规划应用举例拦截导弹（mis）：第1问、第2问分开讨论低价购买（buylow）航线（ship）：既要输出最优解，还要输出达到最优解的不同方案数......三、动态规划例10、最长公共子序列（LCS）题目描述:给定两个序列X、Y，长度不超过5000。请求出两个序列的最长公共子序列。子序列不是字串（不要求连续）。两个字符串cnblogs和belong的公共子序列为blog。可以发现最长公共子序列是不唯一的，但是长度一定是唯一的，比如这里的最长公共子序列的长度为4。样例输入:cnblogsbelong样例输出:4三、动态规划状态设计：

F[i][j]表示X序列前i个元素和Y序列前j个元素的LCS。状态转移方程：三、动态规划跟踪样例体会二维DP的求解过程三、动态规划跟踪样例体会二维DP的求解过程三、动态规划以上算法时间复杂度为O(len1*len2)，已经比较优了。空间复杂度可不可以优化呢？采用类似于杨辉三角形的做法：滚动数组：2个一维数组分别存放当前行和上一行，迭代。一个数组：从后往前计算。三、动态规划例11、合唱队形（CHORUS）题目描述：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…K，他们的身高分别为T1，T2…TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。n<=1000。

题目缺陷：T1<...<Tn或递减的也算合唱队形。三、动态规划样例输入：8186186150200160130197220样例输出：4讨论分析：最后的合唱队形一定是什么情况？一个递增序列(DP1)+一个递减序列(DP2)！那么，中间那个最高的是哪一位同学呢？穷举中间这位同学i。三、动态规划但是，如果先枚举中间最高的那个人，接着对它的左边求最长上升序列，对右边求最长下降序列，那么，总的时间复杂度为O(n^3)，n=1000还是比较危险的。分析发现：我们只需要先求好最长上升DP1[1..n]和下降序列DP2[1..n]，然后再枚举中间最高的同学，每一种合唱队形的长度为DP1[i]+DP2[i]-1，打擂台取最大值ans,答案为n-ans。这样的时间复杂度为O(n^2)。如果本题的n<=10^6呢？进一步优化：利用单调队列优化到O(n*log2n)，三、动态规划例12、加工小木棍（STICK）问题描述：