算法：动态规划-斐波那契数列_斐波那契数列动态规划

简介

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
数学方式表示如下：

对于问题的求解代码想必大家早已耳熟能详，但这里只是借助斐波那契数列作为学习动态规划的例子。通过例子了解动态规划的一些特征。

动态规划：

先看下百度给的定义：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
根据上述描述，可以了解到，动态规划类似分治，同样是将原问题分解成子问题，通过求解子问题而得到原问题的解。但不同的是，动态规划是自底向上分解，并且会保存子问题的解，在需要时可直接拿过来使用，这一点是区别于分治的。通过对子问题解的保存，可以避免大量重复计算，从而提高运行效率。例如上述斐波那契数列，由数学公式得到：当n>1时，第n项是前两项结果的和。如下图所示：

求F（6）时，需要频繁使用之前的结果，因此在计算较小项时，通过对其保存，可以大大提高计算速度。

斐波那契求和
递归版

int fibo2(int n){
 	if(n == 1 || n == 2) return 1;
 	return fibo2(n-1) + fibo2(n-2);
}
1
2
3
4

通过分治法，将求解第n项划分为一个个小的子问题，通过对子问题解的合并，得出原问题的解。结果的正确性毋庸置疑。但是如上述分析，分治的过程时不记录子问题的解的，但是斐波那契求和需要频繁的使用子问题的解，因此，分治方法求解过程的性能令人堪忧。

动态规划版

int fibo(int n){
 	if(n < 1) return -1;
 	int F[n+1];
	F[1] = 1;
 	F[2] = 1;
 	for(int i = 3; i <= n; i++){
  		F[i] = F[i-1] + F[i-2];
 	}
 	return F[n];
}
1
2
3
4
5
6
7
8
9
10

同样是将原问题划分为一个个子问题，通过子问题的求解得到原问题的解。但不同的是子问题求解过程中对解的保存，上述求F(6)时直接寻秩找到F(5)和F(4)的解即可得出，而F(4)和F(5)的解向前递推，从而避免大量的重复计算。可以比较下上述两者的求解速度。

同样求F(1000)，动态规划版可以快速给出求解结果，而递归求解则遥遥无期。因此动态规划的优势不言而喻。

动态规划分析
上述例子分析：
引起上述巨大差异的原因究竟在哪？可以分析下递归求解的过程发现其求解过程入上述树状图所示，各个子问题是互不干涉的，因此造成大量的重复计算。

动规特性
最优子结构：即原问题的最优解包含了子问题的最优解（贪心算法同样具备）
子问题重复：这个特性并不是动规的必要条件，但是子问题重复可以体现动规的优势
仍以斐波那契求解为例说明上述两条特性。斐波那契任意一项(n > 1)的结果，都包含前面子问题的解。通过对子问题的保存，从而避免了大量的重复计算，整体上提高了计算速度。