广告
基础
DFS,深度优先搜索,是一种在搜索中较为常见的算法。主要用于解决“选和不选”和”选几个“的问题,通过一个choose数组和多次递归操作,解决问题。DFS一般是这样的:
从上述模板当中可以看出,DFS一般来说需要几个必要变量:
1.一个正整数n,用于表示数组长度。
2.需要计算的数组a。
3.一个数组choose。
此外,在许多题目中,由于并不是每组数据都合法,所以DFS一般来说会与一个check()函数共同出现。check()函数用于检查每一组DFS的结果是否合法。答案一般是一个全局整型变量,也就是一部分题目中的
特别地,ans变量一定要开在check函数前面,否则会导致平时所说的”先用后付“———先使用后定义的错误,以至于程序无法正常运行。
那么下面展示一道简单的DFS题目的解法:(题目A140-数字全排列):
所以,DFS其实可以被理解成是一种进阶的递归,通过多次递归,计算出答案。
提高
DFS算法一般来说只在CSP-J组中考察,由于时间复杂度较高,它在难题中一般用于解决部分分的骗分问题。也就是说,DFS在CSP-S及以上的比赛中,只能被用于暴力代码,进行对拍或者部分分解决。
参加过2025小码王集训营的可以去那个团队的题库里找到一道名叫”众最大数“的题目。这道题目的正解是通过求数组最大值得到的,此处不再展示。这道题就可以通过DFS获得30%的分数,有兴趣的可以自行尝试一下。
好啦,以上就是全部内容,感谢观看!