斐波那契数列
- 题目描述
- 思路
- 实现
题目描述
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
思路
斐波那契数列概念:第0项为0,第1项为1,从第二项开始:f(n)=f(n-1)+f(n-2)
可以递归,但太慢,这是典型的动态规划题,所以用动态规划解决吧
实现
public int Fibonacci(int n) {
//动态规划
//特殊情况
if(n<2) return n;
//dp[i]数组表示第i个元素的值
int[] dp=new int[n+1]; //下面for循环中i会到达n,所以分配的空间应该至少n+1
dp[0]=0;
dp[1]=1;
//斐波那契数列从第2项开始:f(n)=f(n-1)+f(n-2)
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}