DFS

1 Basic

• 深度优先搜索（Depth-first Search）中，90%的问题，不是求组合（Combination）就是求排列（Permutation）

• 组合问题可以参考全子集问题，排列问题可以参考全排列问题

• Backtracking是DFS中一个非常重要的部分，经典题目需要非常熟练掌握

• DFS经常需要进行Deep Copy来传入搜索的结果

• 利用DFS进行暴力枚举也是一种常见的情况

• 通常结果数目就是时间复杂度

2 Search/Traverse

• DFS更多的还是作为搜索算法，可以递归的进行遍历，没有返回值

• 或者作为某些条件下的遍历

• 也可以在递归的时候进行分治算法，有返回值，如果有重复子问题或者优化结构，可以引入memo表

3 Memo

• 一个很重要的内容是记忆化，可以延伸至Top-Bottom的动态规划的一类问题

4 Path

• 最短路径

• 指定路径

• 图相关问题