上图为利用递归计算5的斐波那契的值时的计算过程 可以看出仅仅计算fib（5）时重复计算的次数就如此之多，所以想办法消去重复的计算。
这个为没有经过优化前的递归：
#include<stdio.h> long fib(int n){ if(n==0){ return 0; } if(n==1){ return 1; } return fib(n-1)+fib(n-2); } int main(){ int n=40; long res=fib(n); printf("%d",res); return 0; }这个是经过优化后的代码：
#include<stdio.h> //记忆化搜索 __int64 memo[10001]; //设立数组memo 大小根据题目实际大小来变化 __int64 fib(int n){ if(n==0){ return 0; } if(n==1){ return 1; } if(memo[n]==-1){ //如果memo为-1 说明当前这个数没有被计算过 ，需要递归来计算 memo[n]=fib(n-1)+fib(n-2); } return memo[n]; //如果memo不为初始化的-1，则说明这个数被计算过 则不需要重新进行计算 } int main(){ int n=1000; for(int i=0;i<=n+1;i++){ //将memo数组初始化为-1 因为fib中的函数结果不可能为负数 memo[i]=-1; } __int64 res=fib(n); printf("%I64d",res); return 0; }第一个程序的时间复杂度是指数级增长，差不多为O(2^n)，计算到40-50之间就会非常慢；
第二个程序时间复杂度已经特别低了，差不多控制在O(n)，计算1000的都可以算快速出来。//此时需要注意的是计算1000时可能会溢出。所以我用了__int64（和long long一样）来定义 输出用的I64d%
记忆化搜索的本质还是递归，只是消去了重复的运算。
递归——自上而下的解决问题
对于多数问题，自上而下的解决比自下而上的解决会简单
但是这个题利用自下而上也是非常简单
动态规划——自下而上的解决问题
#include<stdio.h> __int64 fib(int n){ __int64 a[n]={0}; a[0]=0; a[1]=1; for(int i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } return a[n]; } int main(){ int n=1000; __int64 res=fib(n); printf("%I64d",res); return 0; }这个的时间复杂度也为O(n);和记忆化搜索以后的时间复杂度差不多，但是动态规划不会使用递归，递归会占用栈空间，容易栈溢出；而且这样对a[]的访问真正的做到了只访问一次（对fib n次），而记忆化搜索对memo的访问还是有重复（对fib 2n-1次），所以这个算法更为好。
——————网上看视频课自己写下来的一些小知识点，如有不对，望指出
