题目描述

斐波那契数列
题目的递推公式是：
f(n) = f(n-1) + f(n-2)

样例

/参考代码/

int Fibonacci(int n){
    int i, a[40];
    a[0]=0;
    a[1]=1;
    for(i=2;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    return a[n];
}

算法分类

基本算法之“递推算法”

时间复杂度

时间复杂度O(n)

总结

递推算法思想