DFS

DFS全局变量记录最值

原理

每次DFS过程的时候都搜索到状态树的叶子节点，如果找到了答案就更新一下全局变量记录的最值，当搜索完整棵树的时候，就得到答案了。这种DFS的实现一般来说没有返回值，但是需要每次进行剪枝，如果答案已经比当前最优答案差了，就没有必要再搜下去了。

模板

int ans = 0;
void dfs(int u, int sum)
{
    if (sum > ans) return;
    if (u == n)
    {
        ans = max(ans, sum);
        return;
    }
    //dfs进一步的逻辑
}

DFS迭代加深

原理

用BFS的思想来写DFS就是迭代加深，相当于每次搜索的时候，一层一层的搜索整颗树。用depth来标志搜索到哪一层了。适合答案比较浅的情况，理论来说会产生重复搜索，如果答案较深的话，不适合。这里的剪枝可以叫做乐观估计函数，即搜到多少肯定就没戏了。

模板

bool dfs(int depth, int u, int sum)
{
    if (sum > depth) return false;//如果超过当前深度就不继续搜了
    if (u == n) return true;//如果搜到底了，那么一定得返回了
    //具体下一步dfs的逻辑
}

int main()
{
    int depth = 0;
    while (!dfs(depth, 0, 0)) depth ++ ;//每次迭代加深一
      cout << depth << endl;
    return 0;
}

例题

AW.187 导弹防御系统（中等）

这题主要看迭代加深和全局记录DFS的解方法