动态规划=分治+存储

实际上，递归通常都是动态规划，递归的过程就是把大问题不停地分解，分解到可以直接得出答案。 每一步计算的答案都保存在了堆栈中，函数返回的时候将使用保存在堆栈中的结果。

实际应用中，需要注意这几点：

  • 问题可以被划分为类似的子问题
  • 问题可以计算初始情况，即问题可以被分解到能够直接得出答案
  • 明确问题的通用的计算过程
  • 每次计算出的中间结果保存下来以供回溯时使用