# 五大算法代码模板（DFS 递归非递归都算上，是六个）

1. Recursion 递归
``````def recursion(level, param1, param2, ...):
# recursion terminator
if level > MAX_LEVEL:
print_result
return

# process logic in current level
process_data(level, data...)

# drill down
self.recursion(level+1, p1, p2, ...)

# reverse the current level status if needed
reverse_state(level)
``````
1. DFS(递归写法)

``````visited = set()
def dfs(node, visited)
visited.add(node)
# process current node here.
...
for next_node in node.children():
if not next_node in visited:
dfs(node, visited)``````
2. –DFS(非递归写法)

``````def dfs(graph, start, end):
stack = []
visited = set()
stack.append(start)
while stack:
node = stack.pop()
visited.add(node)
# process current node here
...
for next_node in node.children():
if not next_node in visited:
stack.append(next_node)``````
3. BFS

``````def bfs(graph, start, end):
queue = Queue()
visited = set()
queue.enqueue(start)
while queue:
node = queue.dequeue()
visited.add(node)
# process current node here
...
for next_node in node.children():
if not next_node in visited:
queue.enqueue(next_node)``````
4. binary search

``````l, r = 0, len(array) - 1
while l <= r:
mid = l + (r - l) // 2
if  array[mid] == target:
# find the target!
break or return result
elif array[mid] < target:
l = mid + 1
else:
r = mid - 1``````

二分查找还有几种变形，想法类似。第一个大于、大于等于、小于、小于等于的数

5. DP

``````// 状态定义
dp = new int[m+1][n+1]
// 初始状态
dp[0][0] = x;
dp[0][1] = y;
...
// DP状态推导
for i  = 0; i <= n; ++i {
for j = 0; j <=  m; ++j {
...
dp[i][j] = min{dp[i-1][j], dp[i][j-1], etc.}
}
}
return dp[m][n] // 最优解``````

(=￣ω￣=)··· 暂无内容！

6

0

3

1