分治 && 回溯


代码模版

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

技巧

找到最近最简方法,将其拆解成可重复解决的问题
数学归纳法思维(人肉递归低效、很累 , 抵制人肉递归的诱惑)

本质

寻找重复性 -> 计算机指令集

leetcode

22. 括号生成
50. Pow(x, n)