week03学习笔记

1. 总结
2. 知识
3. 刷题

第三周学习

1. 总结

这周学习了泛型递归，分治和回溯，理解起来不是很难，但是做题总是没有思路，递归这块还是有很多好题目，回溯的八皇后就很有意思

2. 知识

2.1 泛型递归

自己调自己
重复性（找最小重复单元）

代码模版

def recursion(level, param1, param2, ...):
  # recursion terminator
  # 递归终止条件
  if level > Max_level:
      process_result
      return
  # process logic in current level
  # 处理逻辑
  process(level, data...)
  # drill down
  # 递归调用（下钻）
  self.recursion(level+1, p1, p2,...)
  # reverse the current level status if needed
  # 清理变量，一般不需要，但是不能忘记

思维要点
1. 不要进行人肉递归（最大误区）
2. 找到最近最简方法，将其拆解为可重复子问题
3. 数学归纳法思维
  2.2 分治
也是递归
找重复性
将大问题分解成一个个小问题
将小问题的结果组合成最终结果

代码模版

# Python
def divide_conquer(problem, param1, param2, ...): 
      # recursion terminator 
    if problem is None: 
              print_result 
              return 
    # prepare data 
      data = prepare_data(problem) 
    subproblems = split_problem(problem, data) 
    # conquer subproblems 
    subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
    subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
    subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
    …
    # process and generate the final result 
    result = process_result(subresult1, subresult2, subresult3, …)
    # revert the current level states