由斐波那契数列引出动态规划

一、斐波那契数列递归方式实现

---

出现很多冗余的计算过程，计算复杂度随着n的大小呈指数增加 

int fib(int n)
{
	if (n == 0 || n == 1)
		return 1;
	return fib(n - 1) + fib(n - 2);

}

int main()
{
	int n = 40;
	time_t start = clock();
	cout << "n= " << fib(n) << endl;
	time_t end = clock();
	cout << "time= "<<double(end - start) / CLOCKS_PER_SEC<<endl;
}

---

利用记忆式搜索的方式，同样的N，用时少很多

记忆式+自上而下的方式

---

int n = 40;
//[0,n]n+1个元素
vector<int> tmp((n + 1), -1);
int fib_1(int n)
{
	if (n == 0 || n == 1)
		return 1;
	return fib_1(n - 1) + fib_1(n - 2);

}
int fib_2(int n)
{
	if (n == 0 || n == 1)
		return 1;
    //初值为-1，是因为所有斐波那契数列的值都不会等于-1
	else if (tmp[n] == -1)
		tmp[n] = fib_2(n - 1) + fib_2(n - 2);
	return tmp[n];

}


int main()
{
	cout << "-----递归方式----" << endl;
	time_t start_1 = clock();
	cout << "n= " << fib_1(n) << endl;
	time_t end_1 = clock();
	cout << "time= " << double(end_1 - start_1) / CLOCKS_PER_SEC << endl;
	
	cout << "-----记忆式搜索方式----" << endl;
	time_t start_2 = clock();
	cout << "n= " << fib_2(n) << endl;
	time_t end_2 = clock();
	cout << "time= "<<double(end_2 - start_2) / CLOCKS_PER_SEC<<endl;
}

---

动态规划+自下而上的解决问题

---

int n = 40;
//[0,n]n+1个元素
vector<int> tmp((n + 1), -1);
int fib_1(int n)
{
	if (n == 0 || n == 1)
		return 1;
	return fib_1(n - 1) + fib_1(n - 2);

}
int fib_2(int n)
{
	if (n == 0 || n == 1)
		return 1;
	else if (tmp[n] == -1)
		tmp[n] = fib_2(n - 1) + fib_2(n - 2);
	return tmp[n];

}
int fib_3(int n)
{
	vector<int>res(n + 1, -1);
	res[0] = 1;
	res[1] = 1;
	for (int i = 2; i < n + 1; i++)
		res[i] =res[i - 1] + res[i - 2];
	return res[n];
}


int main()
{
	cout << "-----递归方式----" << endl;
	time_t start_1 = clock();
	cout << "n的斐波那契数= " << fib_1(n) << endl;
	time_t end_1 = clock();
	cout << "time= " << double(end_1 - start_1) / CLOCKS_PER_SEC << endl;
	
	cout << "-----记忆式搜索方式----" << endl;
	time_t start_2 = clock();
	cout << "n的斐波那契数= " << fib_2(n) << endl;
	time_t end_2 = clock();
	cout << "time= "<<double(end_2 - start_2) / CLOCKS_PER_SEC<<endl;

	cout << "-----动态规划方式----" << endl;
	time_t start_3 = clock();
	cout << "n的斐波那契数= " << fib_3(n) << endl;
	time_t end_3 = clock();
	cout << "time= " << double(end_3 - start_3) / CLOCKS_PER_SEC << endl;
}

---

---