【算法】搜索入门-DFS

递归

• dfs的一个重要内容是递归。
• 可以理解成自己调用自己的过程。

递归

eg：从前有座山，山里有座庙，庙里有个老和尚在讲故事：从前有座山，
山里有座庙......
以上便是一个递归的过程，显然如果不做任何要求，那么这个过程会一直
重复下去。
所以必须要有终止条件/边界。
对于上例而言，可以规定到日落时结束讲故事。

注意事项

• 调用自身
• 终止条件/边界
• 回溯

DFS框架

斐波那契数列

• 对于当前要求解的f(now)
• now 为1或2，则由题意，返回1即可
• now大于2，则返回f(now-1)+f(now-2)

回溯

在进行深搜的过程中，常常需要标记当前位置是否被访问过，而回溯的过
程即为消除标记的过程。

输出全排列

• 给出一个n，输出1~n的全排列。
• 首先制定搜索方案：全排列为n个数放在n个位置的所有方案，那么可以枚
  举每个位置选择哪个数字。
  例如： n=3时，
  1 2 3
  1 3 2
  2 1 3
  2 3 1
  3 1 2
  3 2 1
  
  

dfs代码实现如下：

dfs(int now)表示查找第now个位置可以放哪个数字（从小到大选取）。
ans[i]表示第i个位置选取的数字。
vis[i]表示数字i是否被选取，值为1表示选取， 0为未选取。

剪枝

	在一些大规模搜索的问题中，采用直接搜索所有方案的方法可能会比较低
效，导致时间超出限制。
	所以可以根据问题的某些性质，针对性的在dfs()函数中进行判断优化， 从
而达到节省时间的效果。

经典寻路问题

NOIP2003 加分二叉树