Get the Kth number in the Fibonacci Sequence. (K is 0-indexed, the 0th Fibonacci number is 0 and the 1st Fibonacci number is 1).
Examples
0th fibonacci number is 0
1st fibonacci number is 1
2nd fibonacci number is 1
3rd fibonacci number is 2
6th fibonacci number is 8
Corner Cases
What if K < 0? in this case, we should always return 0.
Is it possible the result fibonacci number is overflowed? We can assume it will not be overflowed when we solve this problem on this online judge, but we should also know that it is possible to get an overflowed number, and sometimes we will need to use something like BigInteger.
首先想到的是用recursion來(lái)做，但是發(fā)現(xiàn)會(huì)出現(xiàn)recursion次數(shù)過(guò)多的的情況浑侥，之后改用數(shù)組存儲(chǔ)的方式完成更加方便
Recursion：
class Solution(object):
def fibonacci(self, K):
if K <= 0:
return 0
if K == 1:
return 1
res = self.fibonacci(K-1) + self.fibonacci(K-2)
return res
array存儲(chǔ)：
class Solution(object):
def fibonacci(self, K):
num = [0,1]
if K <= 0:
return 0
if K == 1:
return 1
for i in range(0,K-1):
num.append(num[-1] + num[-2])
return num[-1]
