斐波那契数列
斐波那契数列是这样的一个数列：1,1,2,3,5,8,13,21,...,这个数列从第3个数开始，每个数都等于前面两个数的和。这个数列与大自然中植物的关系极为密切，几乎所有花朵的花瓣都来自这个数列中的一项数字，同时在植物的叶、枝、茎等排列中也存在斐波那契数列。
递归模型：
递归实现求第n项：
#includeiostreamusingnamespacestd;//自定义递归函数,intf(intn){//递归边界条件当n==1
n==2if(n==1
n==2){return1;}//从上向下想求第n项，假设n-1项和n-2项可求，依次向下假设推进returnf(n-1)+f(n-2);}intmain(){intn;cinn;coutf(n)endl;}
拆解递归过程：
假设输入n的数值为6，递归过程中发现会出现重叠子问题：
程序验证重叠子问题：
#includeiostreamusingnamespacestd;intnum=0;//定义验证标记intf(intn){//验证标记numnum++;if(n==1
n==2){return1;}returnf(n-1)+f(n-2);}intmain(){intn=6;f(n);//输出总的调用次数coutnumendl;}
把右半边的递归又重复走了一遍，15次：
重叠子问题对时间复杂度的影响：
程序验证对比：
#includeiostream#includectime//滴答次为一秒，滴答一次1ms，这里的滴答可以联想人的心脏跳动，cpu就是电脑心脏，跳动都是以ms计。#defineCLOCKS_PRE_SECusingnamespacestd;intf(intn){if(n==1
n==2){return1;}returnf(n-1)+f(n-2);}intmain(){intn=20;//分别使用测试//定义开始时间time_tstartTime=clock();coutf(n)endl;time_tendTime=clock();cout"时间："double(endTime-startTime)/CLOCKS_PRE_SEC"秒"endl;}
当n为20时，测试时间为0.秒：
当n扩大2倍为40时，测试时间为0.秒：
当n扩大2.5倍为50时，测试时间为54.秒：
结论：通过对比发现，时间的增长根本不是倍数级增长，而是指数级增长！
解决方法：
第一种：在自上向下搜索过程中，对重叠子问题提前保存，当再一次遇到直接返回，不需再重新递归，简称记忆化搜索。
当n为40时，结果运行时间却接近于0，提升显而易见！
第二种：动态规划------自下而上的解决问题
两种方法对比：
递归：
1、递归属于函数的调用，是要占用系统的空间的
2、递归过程中，出现重叠子问题，函数又出现了重复调用
动态规划：
1、循环迭代期间，数组下标对应的空间访问了一次
2、不需要使用函数额外的开辟和占用空间
动态规划：将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。
动态规划：爬楼梯问题
有一个楼梯，总共有n阶的台阶。每一次，可以上一个台阶，也可以上两个台阶。问，爬上这样的一个楼梯，一共有多少不同的方法？
当台阶n=3时，可以有这几种爬楼梯方法：
第一种：一次爬一阶----爬三次
第二种：一次爬一阶，再一次爬两阶----先爬1，再爬2
第三种：一次爬两阶，再一次爬一阶----先爬2，再爬1
递归解决方法：
图解：把大问题依次向前推进一步，假定前面的问题已解决，直到真正遇到已解问题。
记忆化搜索解决重叠子问题：
#includeiostreamusingnamespacestd;intp(inta[],intn){//只有一个台阶时，只有一种走法if(n==1){return1;}//只有两个台阶时，既可以一次一阶，也可以一次两阶if(n==2){return2;}//大问题化解为：一次爬一节到达n，也可以一次爬两节到达nif(a[n]==0){a[n]=p(a,n-1)+p(a,n-2);}returna[n];}intmain(){intn=3;inta[n+1]={0};coutp(a,n)endl;return0;}
动态规划解决重叠子问题：
#includeiostreamusingnamespacestd;intp(inta[],intn){//只有一个台阶时，只有一种走法a[1]=1;//只有两个台阶时，既可以一次一阶，也可以一次两阶a[2]=2;//大问题化解为：一次爬一节到达n，也可以一次爬两节到达nfor(inti=3;i=n;i++){a=a[i-1]+a[i-2];}returna[n];}intmain(){intn=3;inta[n+1]={0};coutp(a,n)endl;return0;}一只小跃跃