LintCode Q366 Fibonacci memoization in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年11月10日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
# @param n: an integer
# @return an integer f(n)
def fibonacci(self, n):
# write your code here
# find fibonacci using recursive with memoization
# fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, ...]
if n <= 1:
return 0
memo = [0] * n
return self.findNthFib(n, memo)
def findNthFib(self, n, memo):
if n == 2 or n == 3:
return 1
else:
fib = memo[n-1]
if fib == 0:
fib = self.findNthFib(n - 1, memo) + self.findNthFib(n - 2, memo)
memo[n - 1] = fib
return fib
else:
return fib
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。