image.png
本质就是找重复性、拆分子问题

分治代码模板

  1. def divide_conquer(problem, param1, param2, ...) :
  2.   # 递归终止条件
  3.   if (problem) is Node: your_logic return
  5.   # 准备数据
  6.   data = prepare_data(problem)  
  7.   # 根据问题将数据拆分若干个子问题
  8.   subproblems = split_problem(problem, data)
  10.   # 攻克子问题
  11.   subresult1 = self.divide_conquer(subproblems[0], p1, ...)
  12.   subresult2 = self.divide_conquer(subproblems[1], p1, ...)
  13.   subresult3 = self.divide_conquer(subproblems[2], p1, ...)
  15.   // 处理并生成最后的结果
  16.   result = process_result(subresult1, subresult2, subresult3, ...)

回溯

试错思想，它尝试分步地去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答时，它将取消上一步甚至上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
回溯通常使用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  1. 找到一个可能存在的正确答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。