关于深度优先搜索(DFS) 与 选择问题_void dfs(int now) { cout << char(now); if (e[now][

本篇主要梳理深度优先搜索与选择问题之间的联系，深剖解题规律。

之前的接触到的搜索都是纯粹的搜索 ，直接就是路径问题。经过这两天的练习我发现DFS在选择问题上是个不错的解决方法。在路径问题上，由于要找到好的路径，所以DFS必须要把所有的路径都找一遍。而到了选择问题，经过简单的转变DFS也可以将所有的选择方案给找出来。路径问题中通过不同的拐点有不同的路，而选择问题中每次不同的选择也代表了一次\"拐点\"。写了几道题发现其实这类题有一定的解题规律，下次遇到此类型的题时可以向搜索靠拢。

数的划分

来源：P1025 NOIP 2001 提高组] 数的划分 - 洛谷

本题就是经典的分配问题，将n个小球分为k份，可使用DP和DFS两种方法，不多做解释

DP解法

int main() { int n, k; cin >> n >> k; int dp[201][7] = {0}; // dp[i][j] 表示将i分成j份的方案数 dp[0][0] = 1; // 初始条件：将0分成0份的方案数为1 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { if (i >= j) dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];//至少有一个1/全都大于1 } } cout << dp[n][k] << endl;

DFS解法

void dfs(int l, int p, int sum)//l为上一个数,p为分的份数,sum为此时的和{if(p==m+1){if(sum==n) ans++;return ;}//为了保证不重复让序列处于非递减,l为上一个数for(int i=l; i+sum<=n; i++) dfs(i,p+1,sum+i);}void solve(){cin >> n >> m;//总数,份数dfs(1,1,0);cout << ans;}

方格填数

来源：P1406 方格填数 - 洛谷

本题意思很简单，给你n*n个数，请你填满 n * n的方格。

这里我们直接遍历整个数组，让它随便填。注意使用标记数组别让它重复就行了。

// Problem: P1406 方格填数// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P1406// Memory Limit: 125 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)int a[N*N],v[N*N];int mat[N][N];int n,m;int sum;string s;bool pan()//此时矩阵已经填完了,判断是否符合条件{int cnt=0;for(int i=1; i<=n; i++)//横排{cnt=0;for(int j=1; j<=n; j++)cnt+=mat[i][j];if(cnt!=sum) return 0;}for(int j=1; j<=n; j++)//竖排{cnt=0;for(int i=1; i<=n; i++)cnt+=mat[i][j];if(cnt!=sum) return 0;}cnt=0;for(int i=1; i<=n; i++)//对角线cnt+=mat[i][i];if(cnt!=sum) return 0;cnt=0;for(int i=1; i<=n; i++)cnt+=mat[n-i+1][i];if(cnt!=sum) return 0;return 1;}void dfs(int x, int y, int z){if(y==n+1)//此行已经填完了{y=1;x++;if(z!=sum)//每一行都进行检查达到\"剪枝\"效果{z=0;return ;}//return表示回溯,但exit(0)就直接结束了z=0;}if(x==n+1){if(pan())//不仅矩阵填完了还完全符合条件就输出,然后直接退出程序{for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)cout << mat[i][j] << \' \';cout << endl;}exit(0);}else return ;//回到上一步}for(int i=1; i<=n*n; i++){if(!v[i])//如果这个点没访问过{v[i]=1;mat[x][y]=a[i];dfs(x,y+1,z+a[i]);v[i]=0,mat[x][y]=0;//回溯回来之后清除上一次的操作}}}void solve(){cin >> n;for(int i=1; i<=n*n; i++) cin >> a[i],sum+=a[i];sum/=n;cout << sum << endl;sort(a+1,a+n*n+1);//保证有序dfs(1,1,0);//起始x,y和此行的和return ;}

猫粮规划

本题是一个经典的01背包，有一点不一样的是它只要达到那个区间就行了。像我这种刚入门DP的蒟蒻加上这么个条件就看不出来了。。。可以用DP和DFS两种方法去解决，可以根据这道题参悟一下DFS在选择方面的使用技巧。

DP解法

dp数组本来求的就是达到n的方案数，原本是只有一个target，一点点从前往后推到 target就行了。本题属于好几个target，只需要简单的将这几个加起来就行了

void solve()//普通01背包问题{cin >> n >> l >> r;for(int i=1; i<=n; i++){cin >> x;w.push_back(x);sum+=x;}if(sum<l){cout << 0;return ;}vector<int> dp(r+1);dp[0]=1;for(int i:w)//数组元素在外循环正序{for(int j=r; j>=i; j--)//target在内循环倒序dp[j]+=dp[j-i];}for(int i=l; i<=r; i++) ans+=dp[i];//区别就在于将这个区间的加上就行了cout << ans;}

DFS解法

DFS解法就没什么好说的，其实比较模板化，到后面进行一个小小总结。

void dfs(int k, int sum){if(sum>r) return ;//搜索容易TLE,记得剪枝if(k==n+1)//注意开大一个,第n个还没选,当n+1的时候才选了n次{if(sum>=l&&sum<=r)//判断条件cnt++;return ;}dfs(k+1,sum+w[k]);//选dfs(k+1,sum);//不选}void solve(){cin >> n >> l >> r;for(int i=1; i<=n; i++)cin >> w[i];dfs(1,0);//第1份食物,总和为0cout << cnt;}

考前抱佛脚

来源：P2392 kkksc03考前临时抱佛脚 - 洛谷

本题其实也是个选择问题，只是之前都是选与不选或按什么选，本题是选给谁。其实都是大差不差，每次选择都相当于一次拐点。还有就是本题看着循环非常多，其实那四个学科都是一样的，只是重复了。由于是多次，为了减少代码量用了二维数组，在看的时候可能会感觉稍微有点复杂

void dfs(int x, int y)//此时是第x科,本科处理了几个{if(y==s[x]+1)//此时当科已经处理完了,要进行判断{minn=min(minn,max(l,r));return ;}l+=a[x][y];dfs(x,y+1);//放左边l-=a[x][y];//回溯时恢复状态r+=a[x][y];//放到右边dfs(x,y+1);r-=a[x][y];}void solve(){for(int i=1; i<=4; i++) cin >> s[i];for(int i=1; i<=4; i++){minn=INT_MAX;l=0,r=0;for(int j=1; j<=s[i]; j++)cin >> a[i][j];dfs(i,0);ans+=minn;}cout << ans;}

小结

写这篇文章的初衷是更好的使用DFS来解决一些选择问题。毕竟DP非常的考验思维，DFS其实还是算比较暴力的方法，并且有一些规律可循。

但是呢DFS支持的数据范围还是比较小的，因为它是利用递归，时间复杂度是呈指数级增长的，在数据范围大的题目中非常容易超时。DP的解法非常考验思维，并且有时要开到二维数组，这种空间换时间的操作也有可能造成内存超限。

下面简单剖析一下DFS解法的一些技巧。

一般来说DFS的大概流程是先在主函数中进入，进入dfs函数之后首先进行判断，如果此时已经搜索完成达到条件就要跳出递归了。与此同时也可以进行剪枝，如果在中途此条路就不对的话及时进行回溯(后悔)。这样就避免了后面再进行指数级的搜索。

之后就是控制进行下一次递归的操作。如果只是选与不选的话直接放两个dfs就行了，这样已经可以包含所有的情况。如果是像方格填数和考前抱佛脚这两个，所有的都要填但是需要满足特定的规则。这样的话就需要进行一定的回溯（后悔操作），这个时候就要进行一定的恢复操作，比如填方格：进入的时候用v数组进行标记说明填过了，但是在dfs函数后边又将v数组恢复了。这个操作就是预判了回溯，如果这个选择是不对的回溯回来把前面做过的操作给清楚掉，就当没走过，不影响后面再进行搜索。

还有就是下一个递归的数怎么选。这就要简单看一下题上的要求。比如数的划分，我就要求它是非递减的，那么dfs就在从l开始的循环中，永远都不会递减。再看方格填数，它的题意是你随便选，但是别重复就行了。那就直接遍历整个数组，用v数组进行标记保证不会重复就行。再说猫粮规划，元素已经非常清楚了，就是那几个。递归的方向无非就是选与不选，直接将两种情况列出来就行了。最后看考前抱佛脚，它是总共就这些元素，看到底哪个分给哪个。那就每次把这两个情况列出来进行递归就行了。

以上就是对DFS的一些思考和总结，如果有其他规律还会进行更新。