1 /* 2 斐波那契的递归实现和记忆化思想 3 在动态规划中，常常会涉及斐波那契数列 4 下面介绍斐波那契的循环打表，递归的实现、打表 5 借鉴自《挑战程序设计竞赛》 6 */ 7 #include
     
       8 using namespace std; 9 const int maxn = 40;10 int f[maxn+5];11 /*12 void fib(int n)//循环打表13 {14     f[1] = f[2] = 1;15     for(int i=3; i<=n; ++i)16         f[i] = f[i-1] + f[i-2];17 }18 int fib(int n)//递归实现19 {20     if(n <= 1) return n;// f[1] = 1;f[2] = 1;21     return fib(n-1) + fib(n-2);22 }*/23 int fib(int n)//通过数组f记录已经算过的fib24 {25     if(n <= 1) return n;26     if(f[n] != 0) return f[n];27     return f[n] = fib(n-1) + fib(n-2);28 }29 int main()30 {31     for(int i=1; i<=maxn; ++i)32         cout << fib(i) << " ";33     cout << endl;34 }