递归代码模板

  1. public void recur(int level, int param) { 
  2.   // terminator 
  3.   if (level > MAX_LEVEL) { 
  4.     // process result 
  5.     return; 
  6.   }
  8.   // process current logic 
  9.   process(level, param); 
  11.   // drill down 
  12.   recur( level: level + 1, newParam); 
  14.   // restore current status 
  15. }

分治代码模板

  1. def divide_conquer(problem, param1, param2, ...): 
  2.   # recursion terminator 
  3.   if problem is None: 
  4.     print_result 
  5.     return 
  7.   # prepare data 
  8.   data = prepare_data(problem) 
  9.   subproblems = split_problem(problem, data) 
  11.   # conquer subproblems 
  12.   subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  13.   subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  14.   subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  15.   …
  17.   # process and generate the final result 
  18.   result = process_result(subresult1, subresult2, subresult3, …)
  20.   # revert the current level states

动态规划定义（wiki）
动态递推
动态规划关键点

  1. 最优子结构 optin= best of(optn-1, optin-2],
  2. 储存中间状态:opt[]

  3. 递推公式(美其名日:状态转移方程或者DP方程)

    Fib: optl[n]=opt[n-1]+opt[n-2]
    二维路径: opt[i][j] = opt[i + 1][j]+opt[i]j + 1

参考链接