递归模板代码

  1. const recursion = (level, params) => {
  2.         // recursion terminator
  3.       if (level > MAX_LEVEL) {
  4.             process_result
  5.         return
  6.     }
  8.       // process current level
  9.       process(level, params)
  11.       // drill down
  12.       recursion(level + 1, params)
  14.       // clean current level status if needed
  15. }

分治（Divide&Conquer）

  • 一种特殊的递归
  1. const divide_conquer = (problem, params) => {
  2.         // recursion terminator 终止条件
  3.       if (problem == null) {
  4.             process_result
  5.         return
  6.     }
  8.       // process current problem 拆分及处理子问题（递归函数）
  9.       subproblems = split_problem(problem, data)
  11.       subresult1 = divide_conquer(subproblem[0], p1)
  12.       subresult2 = divide_conquer(subproblem[1], p1)
  13.       subresult3 = divide_conquer(subproblem[2], p1)
  14.       ...
  16.     // merge 合并（分治）
  17.     result = process_result(subresult1, subresult2, subresult3)
  19.       // revert the current level status 恢复当前层状态
  20. }

感触

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

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

动态规划 Dynamic Programming

  • Wiki 定义
  • “Simplifying a complicated problem by breaking it down into simpler subproblems”(in a recursive manner)
    • 将一个复杂问题分解为简单的子问题（用一种递归的方式）
  • Divide & Conquer + Optimal substructure
    • 分治 + 最优子结构
    • 一般而言，动态规划会让你求一个：最优解、或最大值、或求一个最少的方式
    • 所以，不需要存所有状态，只需要存最优状态
      • 缓存：状态的存储数组
      • 在每一步把次优的状态淘汰掉，在这一步只保留最优的状态

关键点

  • 动态规划 和 递归或者分治 没有根本的区别（关键看有无最优的子结构）
  • 共性：找到重复子问题
  • 差异性：最优子结构、中途可以 淘汰 次优解