食用说明:较为简洁,只是做一个思路清理,(可能会出错),弥补短板,不是教程,也不会放一些梗或者扯皮什么的
总体基于老师发的深搜问题模型总结,只是在其上进行一个自己的理解,再将其与BFS进行比较
正文:
一.DFS的使用
1.01:
好像没有做过太多这种类型题目的变种?
做到过唯一的两种考察形态就是:
第一种:去一个什么地儿,然后买东西或者走路,有几个商店或者几条路
去或不去,买或不买,换汤不换药
第二种:去倒水或什么饮料,然后有到或不到两种,这种类型会在上面施加一些条件,要多加几个判断
然后唯一没有识别出来的是:考前临时抱佛脚,分为两个大脑,然后去枚举一个题放在左脑思考还是放在右脑思考
2.全排列
这个考察的好像会比01多一点...
基础的考察就是在DFS笔记那一篇里提到的抽奖,然后再难一点就是组合的输出,选数
这也是作者最不擅长的提醒之一(突然想起来好像要再多练一下这个题型)
*八皇后是属于全排列吗?
3.搜索
这个...好像不太难,应该也可以用BFS做的...
可能是多源的...有一题记得比较清楚的是观星,但是好像是用BFS做的...
*有一些比较特殊的,比如:求最大的最小值或者最小的最大值等
二.BFS的使用
BFS好像更容易理解吧...一般用于最短路
比较需要注意的是一些关键词,比如"最短""最少"之类的:
一般就是走迷宫,换密码之类的题目吧...
然后是好心人的友情提醒:
大概就是看数据范围,然后迅速判断.如果说类似于10~30的数据范围,可以先试一下DFS.
886,去试一下新学的方案喽...
我回来了....
看得出来AC狗很激动...但是它先别激动....
这样一想的话,好像DFS和BFS的差别还是比较大的.
放在一起学可能只是因为思路有一点相同:一个是按深度,一个是按广度.
搜易都有FS(First Search)