#|【剑指offer刷题】07--递归与动态规划--斐波那切数列剑指offer|递归与循环|剑指off

题目描述大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
解法1：递推法:

int Fibonacci(int n) { if(n<0) return 0; if(n==0) return 0; else if(n==1) return 1; int s=0; int f1=0; int f2=1; while(n>=2){ s=f1+f2; f1=f2; f2=s; n--; } return s; }

解法2：动态规划法

int Fibonacci(int n) { if(n<0) return 0; int *dp=new int[n+1]; dp[0]=0; dp[1]=1; for(int i=2; i<=n; i++) dp[i]=dp[i-1]+dp[i-2]; return dp[n]; delete[]dp; }

【#|【剑指offer刷题】07--递归与动态规划--斐波那切数列】