算法中的独孤九剑 - Fibonacci的两种解法 - 最简单的动态规划法

通过几天时间的闭关修炼，终于练成算法中的独孤九剑--动态规划法了，哈哈O(∩_∩)O哈哈~。

下面是最简单的动态规划法例子。

求Fibonacci数，最简单的就是利用递归求解。如下面第二个函数两行代码就可以了。

但是这样的话会不断递归，造成很多重复求解，运行速度自然很低。为了提高速度，可以把之前求解到的值保存下来，在下一次循环中重复利用。比如求F(n) = F(n-1) + F(n-2);

F(n-1) =F(n-2)+F(n-3)，求F(n)的时候，如果F(n-1)的值保存了的话，那么就不用重复递归求F(n-1)了。

下面第一个函数就是这样解的，效率就是O(n)了，很高的效率。

这个就是动态规划法的入门基础，简单概括就是：如果计算的结果是后面需要重复用到的话，那么就保存这个结果。

class Solution {
public:
	int fibonacciD(int n)
	{
		if(n==0 || n==1) return 1;
		int last = 1;
		int nextToLast = 1;
		int answer = 1;
		for(int i = 2; i<=n; i++)
		{
			answer = last+nextToLast;
			nextToLast = last;
			last = answer;
		}
		return answer;
	}	
	int fibonacciR(int n)
	{
		if(n==0 || n==1) return 1;
		return fibonacciR(n-1)+fibonacciR(n-2);
	}
};

int main()
{
	Solution solu;

	cout<<solu.fibonacciD(7)<<endl;
	cout<<solu.fibonacciR(7)<<endl;

	cout<<endl;

	return 0;
}

利用动态规划法可以很轻松产生一个fibonacci序列，如下：

void generateFibonacci(vector<int> &fibvec, int n)
{
	fibvec.push_back(0);
	fibvec.push_back(1);
	for (int i = 2; i < n; i++)
	{
		fibvec.push_back(fibvec[i-1] + fibvec[i-2]);
	}
}

int main()
{
	vector<int> fibvec;
	generateFibonacci(fibvec, 20);
	for (auto x:fibvec)
		cout<<x<<" ";
	cout<<endl;

	system("pause");
	return 0;
}