由斐波那契数列与动态规划入门（推荐给那些想学动态规划又半天找不到切入点的同学）

斐波那契数列与动态规划入门

      斐波那契数列在计算机中计算很常见，该数列是一个1，1，2，3，5……往上可到无穷大的数列，其一般公式为：

      由于这样特殊的公式无意中与动态规划（Dynamic Programming，简称DP），方法类似，一般来说我们可以通过斐波那契数列来进行动态规划的入门学习，所谓动态规划，是一种类似于分治的思维，通过组合子问题的解来求解原问题。

      不同的是，分治方法通常将问题划分为互不相交的子问题，递归地求解子问题，再讲它们的解组合起来，求出原问题的解。而动态规划应用于子问题重叠的情况，即不用的子问题具有公共的子子问题。在这种情况下，如果采用分治算法，则分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。对于动态规划法，它对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

      第一次看估计你也和我一样头晕了，那我们且不谈动态规划的实际定义，那些什么状态转移方程都不管先，我们拿实际问题来弄。

       在开始之前，为了统计代码的效率，我利用了C标准库里的<time.h>头文件（由于我用bits/stdc++.h万能头文件，所以这句话被省略了），其中的clock()函数，可以获取到一个当前的时间信息，我们在程序的开头使用这个clock()获取开始时的时间，再在我们想要的地方再次获取一次这个时间，两次相减，就可以得到我们这一段程序运行的时间了。

模板如下：

#include<iostream>
#include<time.h>
using namespace std;

int main(){
	int start,finish;
	start=clock();
	//你要执行的内容
	finish=clock(); 
	cout<<"Running time is: "<<finish-start<<" ms"<<endl;
	return 0;
}

对于求一个斐波那契数列中的某一项，我们一般可以用到递归（或循环）的方式进行解决，通过一个函数可以简单获取

long long fib(int n) {
       long long result;
       return (n<=2)?1:fib(n-1)+fib(n-2);
}

完全的代码如下：

#include<bits/stdc++.h>
using namespace std;
long long fib(int n) {
	long long result;
	return (n<=2)?1:fib(n-1)+fib(n-2);
}
int main() {
	int start,next1,next2;
	start=clock();
	cout<<fib(5)<<endl;
	next1=clock();
	cout<<"Fibonacci(n=5) running time is: "<<next1-start<<" ms"<<endl;
	
	cout<<fib(10)<<endl;
	next2=clock();
	cout<<"Fibonacci(n=10) running time is: "<<next2-next1<<" ms"<<endl;
	
	cout<<fib(35)<<endl;
	next1=clock();
	cout<<"Fibonacci(n=35) running time is: "<<next1-next2<<" ms"<<endl;
	
	cout<<fib(50)<<endl;
	next2=clock();
	cout<<"Fibonacci(n=50) running time is: "<<next2-next1<<" ms"<<endl;
	return 0;
}

     但是这样有一个问题，就是我们会造成大量的重复计算，如图，一个n=5的数列中，fib(3)计算了两次,fib(2)计算了3次,fib(1)计算了2次，这还仅仅是从n=5中看出来的数据，当n等于很大的时候，这个数据计算规模往往会造成超时，实际上，经过计算，这种算法的时间复杂度高达O(2^n)之高，极小数据才可以使用。

再来看一下运行时间：

 这里可以看得出来，当n=35的时候，明显计算量上去了，当n=50的时候，估计就需要我们去喝咖啡了。

这里抛开动态规划严格且抽象的定义，我们从它的实现方式入手，也即记录结果再利用，我们来看动态规划版本的计算方法：

const int maxn=1000005;
long long memo[maxn]= {0};
long long fib(int n) {
       if(n<=2)
              return 1;
       if(memo[n])
              return memo[n];
       else
              return memo[n]=fib(n-1)+fib(n-2);
}

这里完全代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
long long memo[maxn]= {0};
long long fib(int n) {
	if(n<=2)
		return 1;
	if(memo[n])
		return memo[n];
	else
		return memo[n]=fib(n-1)+fib(n-2);
}
int main() {
	int start,next1,next2;
	start=clock();
	cout<<fib(5)<<endl;
	next1=clock();
	cout<<"Fibonacci(n=5) running time is: "<<next1-start<<" ms"<<endl;

	cout<<fib(10)<<endl;
	next2=clock();
	cout<<"Fibonacci(n=10) running time is: "<<next2-next1<<" ms"<<endl;

	cout<<fib(35)<<endl;
	next1=clock();
	cout<<"Fibonacci(n=35) running time is: "<<next1-next2<<" ms"<<endl;

	cout<<fib(50)<<endl;
	next2=clock();
	cout<<"Fibonacci(n=50) running time is: "<<next2-next1<<" ms"<<endl;
	return 0;
}

这里看似好像仍然是之前的递归形式相同，然而，通过查看其递归调用的流程可以发现，分支的右侧，已在左侧计算出且保存在mem[n]中，通过将计算结果并入的方式，可以解决重复计算的问题，最终这个算法的时间复复杂，可以约简为O(n)。

同样的数据，我们拿出来看一下时间：

当然此外我们对于解决斐波那契数列还有很多的方法，正常学习的时候也会遇到过用for强行求，比如说利用通项公式可以直接让复杂度变为O(1)，秒解，但是这样的方法无法应对大数据，面对大数据，我们通常会再开一个数组，或将原数组变为一个二维数组进行求解，这些日后慢慢研究吧。

分享这个东西的主要目的是对于入门动态规划有帮助，斐波那契数列的公式，不正好也是一种状态转移方程么？每一项只受前一项的影响，不也就是一种无后效性的原理？我们看看动态规划DP的三个最主要的性质。

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

 对此，请再度回头去看一下动态规划版本的求斐波那契数列的方法，这个memo[]数组，是否和动态规划dp中的dp[]数组有一种异曲同工之妙？

当你对于这个完全可以理解的时候，可以试着去解决一些基本的动态规划习题，比如说 数塔问题 ，再比如说集合问题， 然后可以试着去归类做一些习题，比如说01背包，01背包的升级版，完全背包之类的。

对于本题，当数据量变大的时候并不能完整的显示出来时，请试一下n=1000000的数据量，完完全全会造成出错，这个时候可以利用大数来杂合这两个问题，但同时引入大数又会造成新的问题……总之，一切自己摸索。

告辞！