关于ACM的深搜和广搜以及动态规划

Question

求推荐几个基本类型的题，还有提供几个比较简单的完整代码做解释，先不考虑剪枝之类的，只是想了解什么是DFS BFS 以及具体哪类题目可以用。如何用代码实现（要用c语言的，本人新手只会c,网上的代码好多c++，c写的又感觉太难。。。（能简单简介一下最好了，本人做的POJ 的sticks题，那个和搜索什么关系？思路是怎么样的？）（提供链接或具体那本书有介绍也可以，回答好的有加分）

Answer 1

你好，亲，这段讲解使我们集训队代课老师给我们的，希望有帮助。
搜索算法阶段性总结：
BFS与DFS的讨论：BFS：这是一种基于队列这种数据结构的搜索方式，它的特点是由每一个状态可以扩展出许多状态，然后再以此扩展，直到找到目标状态或者队列中头尾指针相遇，即队列中所有状态都已处理完毕。
DFS：基于递归的搜索方式，它的特点是由一个状态拓展一个状态，然后不停拓展，直到找到目标或者无法继续拓展结束一个状态的递归。

优缺点：BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高

总结：不管是BFS还是DFS，它们虽然好用，但由于时间和空间的局限性，以至于它们只能解决数据量小的问题。

各种搜索题目归类：

坐标类型搜索 ：这种类型的搜索题目通常来说简单的比较简单，复杂的通常在边界的处理和情况的讨论方面会比较复杂，分析这类问题，我们首先要抓住题目的意思，看具体是怎么建立坐标系（特别重要），然后仔细分析到搜索的每一个阶段是如何通过条件转移到下一个阶段的。确定每一次递归（对于DFS）的回溯和深入条件，对于BFS，要注意每一次入队的条件同时注意判重。要牢牢把握目标状态是一个什么状态，在什么时候结束搜索。还有，DFS过程的参数如何设定，是带参数还是不带参数，带的话各个参数一定要保证能完全的表示一个状态，不会出现一个状态对应多个参数，而这一点对于BFS来说就稍简单些，只需要多设置些变量就可以了。
经典题目：细胞（NDK1435）、Tyvj：乳草的入侵、武士风度的牛

数值类型搜索：（虽然我也不知道该怎么叫，就起这个名字吧），这种类型的搜索就需要仔细分析分析了，一般来说采用DFS，而且它的终止条件一般都是很明显的，难就难在对于过程的把握，过程的把握类似于坐标类型的搜索（判重、深入、枚举），注意这种类型的搜索通常还要用到剪枝优化，对于那些明显不符合要求的特殊状态我们一定要在之前就去掉它，否则它会像滚雪球一样越滚越大，浪费我们的时间。
经典题目：Tyvj：派对；售货员的难题，以及各种有关题目搜索算法阶段性总结

你好，明天可以发你几道这类题，而且还有代码，亲。

追问

谢谢了，想法我懂，就是不知道具体怎么在题中用，Q1544967987,顺便加个好友吧，你们还有集训队啊。。。。。

追答

对啊，你们没有的，我们是老师带领着我们的

追问

额。。。。你东西记得发啊。。。还有记得加好友。。。你是几年级的。。。

追答

不好意思，你说发什么东西？好友加了。我大一