这是数据结构与算法的第二节内容，在讲这节之前，我单独拿出来一个讲解一个很重的算法，下一节，我会拿LeetCode上面的动态规划题来看，先看动态规划
有关动态规划（Dynamic Programming）算法的题目很多。动态规划（Dynamic Programming）算法也算一个比较考验逻辑能力的算法了；
动态规划算法的核心
理解一个算法就要理解一个算法的核心，动态规划算法的核心是什么呢？看下面
最重要的一句话，记住求解的过程，就是找一个数据结构，记下你每一步求解的答案；
动态规划算法的两种形式
上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。
为了说明动态规划的这两种方法，举一个最简单的例子：求斐波拉契数列Fibonacci 。先看一下这个问题，下面就是这个数列的计算方法：
Fibonacci (n) = 1; n = 0
Fibonacci (n) = 1; n = 1
Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)
这道题，给你一个n？让你求Fibonacci (n)？怎么求，最笨的方法是什么呢？直接来个递归是不是？
看递归，这里用java写了（注意语言只是工具）
这个递归你要是看不懂，真得好好补补。是不是逻辑很简单；我们既然研究算法，题是做出来了，但是这样子好吗？
先看看下这个递归的执行流程
.....
看出什么来了吗？我们在求f（6）的过程中，递归了2次f（4），5次f（2）.....
如果数字够大比如1000000000，那么空间和时间上开销，只能呵呵；
有没有什么办法改进呢？当然有动态规划，我说了动态规划最主要的是记录每一步的求解过程，之后我们换个名词叫子问题，就是子问题的解，来看看（是不是脑海中已经快有答案了？子问题不就是前面f（4），f（2）...的值吗?）
①自顶向下的备忘录法
这种方法还是用递归，只不过在递归的过程中，我们把每一个求解完的f（n）给存下来了，比如在求解f（6）的时候，我们先得去求解f（5）和f（4），我再去递归，求f（5），这次我们需要求f（4）和f（3），之后我们先不管，我再往下是不是一定会求出f（4）？我们记录下来这个f（4），等我们回去求解f（6）产生的子问题f（4）的时候，是不是就不用再往下递归，直接用就可以？（好好理解，很简单，因为复杂的再后面）
所以这个时候我们需要一个数据结构记录我们的每一步计算的值？选什么数据结构呢？大家想一下，我们要的这个数据结构只要方便我们查就行？比如我想马上知道f（4）等于多少，不用循环，更不用遍历，最好一下就能找到，毫无疑问最简单的就是数组；
一起看看代码
②自底向上的动态规划
自顶向下还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。记住这几句话，收益匪浅，先解决局部问题，在向着大问题发展；来看看代码
现在动态规划的两种方法都介绍完了，我们来比较下，这两种方法，自顶向下，我们是从大问题先入手，在求解过程中，遇到每个子问题就记录它的值，可以说是被动的；自底向上的过程，就是我们刻意用动态规划，直接从子问题入手，最后求解大问题；
好了，今天就到这里，看来还需要一篇文章，来说动态规划了，下篇文章，如果大家有学习算法和数据结构这方面的兴趣，就关注下，方便大家阅读，和跟上节奏；谢谢大家（文/村里的霸王）
