深度优先搜索（二）
原创
先看个小题热热身。
整数分解 整数分解为若干项之和
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。
输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。
输出格式：
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
输入样例：
7
输出样例：
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
7=2+5;7=3+4;7=7
这种玩意一看就是深搜，通过搜索得到结果。
当时我做的时候碰到的坑点差点卡死我。
坑点1，只注意得到正确的等式，通过搜索（二维数组记录）记录输出正确结果。输出一看，傻了眼，输出了好几千行，原来我的那种DFS保留树的层数，既保留数字顺序，并且为了得到7=7的等式，把0也加了进去，倒置输出结果里面有很多无意义的数字0.改的时候一想这种做法顶多不输出无意义的0，数字顺序依然保留。
坑点2，换了写法之后，样例过了，summit，过了三个点，最后一个点过不去，拿下来一经测试大于20的数编译器无法处理，稍加分析知不可用二维数组储存数据，因为大数的分解方式太多。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,kind=0,m2[100],cnt=0,sum=0,b[100];//n是全局变量。
void dfs(int now){
if (sum==n) {
printf("%d=", n);
kind++;
for (int k=0; k<cnt-1; k++) {
printf("%d+", m2[k]);
}
if( kind%4 == 0 || m2[cnt-1] == n) {
printf("%d\n",m2[cnt-1]);
} else {
printf("%d;", m2[cnt-1]);
}
//不需要继续初始化条件
}
else if (sum>=n) ;//小小优化一下
else
for (int j=now;j<=n;j++){
m2[cnt++]=j;
sum+=j;
dfs(j);
cnt--;
sum-=j;
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
核心是DFS，首先递归和回溯要理解清楚。
输出条件是sum=n；里面全是输出格式控制。怎么做到不是怎后一行就输出一个等式后面加“；”，如果有4个话输出4个加“\n”。如果不够4个怎么输出？最后一个等式不加“+”对吧。规律的发现十分重要的，最后一个肯定是（n==n）情况。
再就是利用程序是顺序执行的。//我认为这是理解dfs必要一环。
注意看这个循环：
for(int j=now;j<=n;j++)
{
m2[cnt++]=j;
sum+=j;
dfs(j);
cnt--;
sum-=j;
}
dfs第一次深搜完（肯定是7=1+1+1+1+1+1+1；）就能从dfs（1）开始执行了，对吧，然后在循环里面把
2赋值给m2[(cnt--)++]，在dfs（2）时直接输出7=1+1+1+1+1+2；就是这么个情况，over。
你说你怎么不会写，那我也没办法，这玩意不好立刻理解，实在不行就通过做大量题顿悟吧。
热身完了，好好的做一个题吧。
（题目作者：徐不可说
来源：CSDN
原文：https://blog.csdn.net/qq_42712462/article/details/81257837）
题目描述
将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的分法。
输入
n，k (6<n<=200，2<=k<=6)
输出
一个整数，即不同的分法
样例输入
7 3
样例输出
4
OK，又是这种通过某种数学运算形成等式的题，不再废话，DFS。
你可能要问了，这个智障作者还在这儿分析用啥算法做这个题，不用DFS/BFS他把题放这儿吗？
嘿嘿嘿，且慢。
下面这句话就要把你打回原形了：搜索的算法时间复杂度大多是指数级的。
这个题的时间限制是1s。怎么样？你还有办法做吗？剪枝！这个名字看着挺专业的，其实也就是个名字，哈哈哈，提一下，我之前做模式字串匹配问题时竟然有个算法叫 BF算法，哈哈哈，可笑死我了，BF算法它还有个更高大上的名字暴风算法(英语Brute Force算法，咦？你这是欺负我不会英语么？明明是暴力的意思呀，哈哈哈。)，干什么的呐？you guess it，就是暴力匹配的意思，没有任何算法可言，但是不妨碍人家有个霸气的名字。其他的算法可能也要名字了，哎，慢着，这和人类一样，你后面得有人（算法）才能让你拥有自己的名字。人家BF算法有个儿子叫KMP算法，可是牛X的很呢。这个叫剪枝的和BF一样，没啥难的，就是叫了个高大上的名字。
一、剪枝策略的寻找的方法
1）微观方法：从问题本身出发，发现剪枝条件。
2）宏观方法：从整体出发，发现剪枝条件。
3）注意提高效率，这是关键，最重要的。
总之，剪枝策略，属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。
二、剪枝优化三原则
正确、准确、高效.原则 搜索算法,绝大部分需要用到剪枝.然而,不是所有的枝条都可以剪掉,这就需要通过设计出合理的判断方法,以决定某一分支的取舍. 在设计判断方法的时候,需要遵循一定的原则.
1） 正确性 正如上文所述,枝条不是爱剪就能剪的. 如果随便剪枝,把带有最优解的那一分支也剪掉了的话,剪枝也就失去了意义. 所以,剪枝的前提是一定要保证不丢失正确的结果.
2）准确性 在保证了正确性的基础上,我们应该根据具体问题具体分析,采用合适的判断手段,使不包含最优解的枝条尽可能多的被剪去,以达到程序“最优化”的目的. 可以说,剪枝的准确性,是衡量一个优化算法好坏的标准.
3）高效性 设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的. 倘若一个剪枝的判断效果非常好,但是它却需要耗费大量的时间来判断、比较,结果整个程序运行起来也跟没有优化过的没什么区别,这样就太得不偿失了.
三、深度优先搜索的优化技巧
1 优化搜索顺序：在一些搜索问题中，搜索树的各个层次，各个分支之间的顺序是不固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
2 排除等效冗余：在搜索过程中，如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
3 可行性剪枝（上下界剪枝）：该方法判断继续搜索能否得出答案，如果不能直接回溯。 在搜索过程中，即使对当前状态进行检查，如果发现分支已经无法到达递归边界，就执行回溯。
4 最优性剪枝：最优性剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。
5 记忆化：可以记录每个状态的搜索结果，再重复遍历一个状态时直接检索并返回。这好比我们对图进行深度优先遍历时，标记一个节点是否已经被访问过。
先看这个代码，这儿只说剪枝的优点。怎么才能写出这样的代码，解题思路在下篇的“摔鸡蛋”题中给出。
#include<iostream>
using namespace std;
int dfs(int n,int k){
if(n==0||n<k||k==0) return 0;//优化
if(k==1||n==k) return 1;//优化
return dfs(n-1,k-1)+dfs(n-k,k);
}
int main()
{
int n,k;
cin>>n>>k;
int x=dfs(n,k);
cout<<x<<"\n";
return 0;
}
我的第一篇简书也是深搜的，敬请阅读。
来都来了，再看一个题吧。
题目背景
题目来源：洛谷
作者：叫我※森哥
猪猪hanke得到了一只鸡
题目描述
猪猪Hanke特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke吃鸡很特别，为什么特别呢？因为他有10种配料（芥末、孜然等），每种配料可以放1—3克，任意烤鸡的美味程度为所有配料质量之和
现在，Hanke想要知道，如果给你一个美味程度，请输出这10种配料的所有搭配方案
输入输出格式
输入格式：
一行,n<=5000
输出格式：
第一行，方案总数
第二行至结束，10个数，表示每种配料所放的质量
按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个“0”
又双叒叕是搜索使等式成立的问题。
以树为结构话，其10层肯定是不会变啦。however，我脚得还得用DFS，中间for (int i=1;i<=10;i++)猛一看想广搜似的，哈哈哈。
#include<iostream>
#include<cstdio>
using namespace std;
int n,cnt,ans[100100][11],sum,a[11];
void dfs(int t,int m)//t代表当前的尝试的调料。m代表当前美味程度
{
if (t>10)
{
if (m==n) //bfs获得等式不可缺少的一步。
{
cnt++;//统计方案总数
for (int i=1;i<=10;i++)
ans[cnt][i]=a[i];//存入答案的数组
}
return ;
}
for (int i=1;i<=3;i++)
{
if (m+i>n) break;//小小优化一下。
a[t]=i;//储存答案
bfs(t+1,m+i);//查看下一种调料
a[t]=0;//状态恢复*真*真*相当重要。
}
}
int main()
{
cin>>n;
bfs(1,0);//广搜开端
cout<<cnt<<endl;
for (int i=1;i<=cnt;i++)
{
for (int j=1;j<=10;j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}
over，这个题巩固一下对搜索的理解，第一题理解懂了，这个题在回溯的地方根本不用多加思考了，但是还是有较大的不同，最大的不同是：第一个题是层数输出数字个数递减、层数数字无序，这个题是层数唯一、层数数字有序。
多做做题吧，骚年。
