算法（二）深度优先搜索DFS

本文简单介绍一下DFS模板

1. 什么时候用DFS或者BFS？

当问题可以拆解为若干个子问题的时候

2. 无状态DFS

无状态DFS，就是遍历过程中，不需要记录前面某一状态的途径的路径。此时利用栈的先进后出原则实现DFS

stack init
while stack:
    top = stack.pop()
    handle(top, handle the case jump out of the loop)
    stack.append(all next state of top node)

3. 有状态DFS

有状态DFS，就是在遍历过程中，需要记录前面节点的状态，所途径的路径。此时需要用递归实现

def dfs(res, curr_node, path, other_params):
    """
    args:
        res: used to store the result. Maybe not needed
        curr_node: current node. Maybe not needed
        path: The path to arrive to this node. Must needed
        other_params: Other params used to do prune or 
    """
    if current node satisfy requirements:
        return result or store the result
    else:
        return dfs(curr_node's next state)