关于递归写在前面

1. 虽然不强制必须写一个小的能解决单一问题的函数，例如mergeSort中，把两个有序的合并成一个新的有序的 又如快排中把第一个数移到左边的数都比他小，右边都比他大的地方，这些基础算法本身和递归无关，但有时候也挺难实现的 但记住，这不是递归的关键，把他分离成另一个函数可以减少你同时思考的量
2. 递归自己调自己，养成习惯这个函数开头就写判断，判断何时不再递归，
3. 递归能解决问题的关键在于那个判断的变量，虽然递归每次都调用一样的函数，但这个函数运行时的变量值肯定是变的，否则就是在无意义的重复 为了思路清晰，最好把这个变化的变量作为递归函数的参数
4. 递归思路（汉诺塔举例）
   1. 假设自己会那个比最大号问题小一号的问题，怎么获得最大号的问题的解（这时候你脑子肯定不知道小一号问题的解，但千万不要细想这点） （汉诺塔：你已经获得了移动n-1块的能力，你可以随便移动）
   2. 想最小问题如何解决，并把它写在递归函数的开头判断上（汉诺塔：移动一块）
   3. 相信自己，现在你已经可以知道怎么解决问题了，不管你现在内心是否清晰

略复杂，主要理解概念，具体其实只要没超过int最大值，用内置乘法还是最快

数学问题啊啊啊啊啊，，太难了，放弃

这个问题有点难，知乎有很多优秀回答值得参考
写在前面，以我目前粗浅的理解，第一次接触到实在著名的斐波拉契数列中 简单来说就是递归/分治+使用内存来存下运行时数据，防止同样的问题算很多遍，以提升效率 这也是维基百科定义的

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

说重点！！ 这个教科书上在说啥，，我实在是看不懂

4. 到这里就可以说明一下动态规划与递归、caching的关系，（1）递归只是动态规划的一种实现方式，属于“自顶向下”的实现方式。一个动态规划问题在实现的时候完全是可以用非递归的方式来编码实现的。所以，递归不是动态规划的本质。（2）Caching是动态规划实现过程中提升计算效率的一种方法，它的想法就是把计算过的值存起来，下次同样的计算过程直接使用保存的结果即可。Caching既可以用于递归实现，也可以用在非递归实现。所以，Caching也不是动态规划的本质。

看到这，，就不明白递归和。动态规划了。。。。。