内存缓存与动态规划

先来看1个动态规划的概念：

任何数学递归公式都可以直接翻译成递归算法，但是基本现实是编译器常常不能正确对待递归算法，结果导致低效的算法（没错说的就是递归）。当我们怀疑很可能是这种情况时，我们必须再给编译器一些帮助，将递归算法重新写成非递归算法，将后者把那些子问题的答案系统的记录在一个表内。利用这种方法的一种技巧就叫做动态规划（dynamic programming）。

这一小节讲到的 【要计算数列中第 n 个数字，需要先得到之前两个数的值】就是上述的子问题， 【第 n 个数的值存在数组中索引为 n 的位置】即那些子问题的答案系统的记录在一个表内。

当然了这里并没有将递归算法重写成非递归算法，只是用数组避免了重复计算，性能的提升已经爆炸了， 因为递归算法中，子问题的计算是指数增长的。 有兴趣的同学可以深入研究一下，这里就不展开了 :）

下面给出一个线性斐波那契数列算法

 package main

 import "fmt"
 func main() {
     fmt.Println(fibonnaci(10))
 }

 func  fibonnaci( limit int) (ret int) {
      if limit  <= 1 {
         return 1
     }
     last , nextToLast := 1 , 1

     var answer int
     for i := 2; i < limit; i++ {
         answer =  last + nextToLast;
         nextToLast = last
         last = answer
     }
     return answer
 }