斐波那契数列

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例 输入整数 n=5 返回 5

递推

时间复杂度O(n)

class Solution { public int fibonacci(int n) { if(n < 2 && n > 0){ return n; } return fibonacci(n - 1) + fibonacci(n - 2); } }

打表法 23333

时间复杂度O(1)

class Solution { int fibonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(n==2) return 1; if(n==3) return 2; if(n==4) return 3; if(n==5) return 5; if(n==6) return 8; if(n==7) return 13; if(n==8) return 21; if(n==9) return 34; if(n==10) return 55; if(n==11) return 89; if(n==12) return 144; if(n==13) return 233; if(n==14) return 377; if(n==15) return 610; if(n==16) return 987; if(n==17) return 1597; if(n==18) return 2584; if(n==19) return 4184; if(n==20) return 6765; if(n==21) return 10946; if(n==22) return 17711; if(n==23) return 28657; if(n==24) return 46368; if(n==25) return 75025; if(n==26) return 121393; if(n==27) return 196418; if(n==28) return 317811; if(n==29) return 514229; if(n==30) return 832040; if(n==31) return 1346269; if(n==32) return 2178309; if(n==33) return 3524578; if(n==34) return 5702887; if(n==35) return 9227456; if(n==36) return 14930352; if(n==37) return 24157817; if(n==38) return 39088169; if(n==39) return 63245986; } }