1 /*
 2 斐波那契的递归实现和记忆化思想
 3 在动态规划中，常常会涉及斐波那契数列
 4 下面介绍斐波那契的循环打表，递归的实现、打表
 5 借鉴自《挑战程序设计竞赛》
 6 */
 7 #include<iostream>
 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记录已经算过的fib
24 {
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 }