LintCode Q111 Climbing Stairs recurisve in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年11月16日
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
"""
def climbStairs(self, n):
# write your code here
# recursive with memoization
if n < 0:
return n
# 1, 1, 2, 3, 5
memo = [1]*(n+1)
return self.fib(n, memo)
def fib(self, n, memo):
if n == 0 or n == 1:
return memo[n]
else:
if memo[n] == 1:
memo[n] = self.fib(n - 1, memo) + self.fib(n - 2, memo)
return memo[n]
else:
return memo[n]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。