题目描述：

斐波那契数列是一个满足:
当x=1，或者x=2时候，fib(1)=1,fib(2)=2;
当x>2时，fib(x)= fib(x-1)+fib(x-2)
求：fib(x),x>0;

题解1.递归-效率低

图示（来自漫漫云天自翱翔）

从图示可见，这种从上往下的采用递归的算法含有大量重复的计算，效率较低。

代码

int fibonacci1(int n) {
	if (1 == n)
		return 1;
	if (2 == n)
		return 2;
	return fibonacci1(n - 1) + fibonacci1(n - 2);
}

题解2：动态规划+数组

“动态规划”的解题思路(引自不是江小白)：

状态转移表法（回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码）；
状态转移方程法（找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码）。

代码

int fibonacci2(int n) {
	if (1 == n)
		return 1;
	if (2 == n)
		return 2;

	int sum[100];//定义一个数组，用来装fib值
	sum[0] = 1;
	sum[1] = 2;

	for (int i = 2; i < n; i++) {
		sum[i] = sum[i - 1] + sum[i - 2];
	}
	return sum[n-1];
}

**题解3：动态规划+临时变量

代码

/*
	采用数组来保存每次计算的值会创建多余的空间，且随着n的增大，数组也会越来越大。
*/
int fibonacci3(int n) {
	if (1 == n)
		return 1;
	if (2 == n)
		return 2;
	int a = 1;
	int b = 2;
	int sum = 0;
	for (int i = 2; i < n; i++) {
		sum = b + a;
		//此处一定要注意：先存放较小的值
		a = b;//a相当于v[i-2]
		b = sum;//b相当于v[i-1]
	}
	return sum;
}