动态规划(1)——斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用

首先观察1、1、2、3、5、8、13、21、34可以写出求斐波那契数列非递归实现

int fib(int n) {
	int f = 1;
	int b = 0;
	while(--n) {
		f += b;
		b = f -b;
	}
	return f;
}

而由F(n)=F(n-1)+F(n-2)公式很容易想到使用递归实现

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

计算可以得出这种递归的时间复杂度是O(2^n)水平，我们将递归树画出如下

可以看出进行了重复的计算，我们想提高效率也就是使得不重复计算，将子问题计算的结果记忆起来。
我们引入一个vector记录计算的结果

vector<int> mem(n+1,-1); 

int fib(int n) {
	if(n==0) return 0;
	if(n==1) return 1;
	if(mem[n]==-1)
		mem[n]=fib(n-1)+fib(n-2);
	return mem[n];
}

使用记忆化搜索，记录斐波那契的值，此时时间复杂度已经是O(n)级别。
我们在使用递归的过程中实际是自上而下的解决问题，而如果我们自下而上的解决问题，即将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案，这就是动态规划

dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. 维基百科-动态规划

使用动态规划代码如下

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

可以知道自上向下的记忆化搜索和动态规划的方法都是O(n)级别的，但在记忆化搜索中fib函数调用了2n-1次而不是n次，而递归调用还花费时间和空间，动态规划的方法实际上每个mem只访问了一下，相比之下自下向上的动态规划是更优的选择。

类似的问题跳台阶（Climbing Stairs）可以转化为斐波那契数列问题，解法是一样的