# 070 Climbing Stairs

### 70. Climbing Stairs

Fibonacci 的DP版本

Memoization will usually add on your time-complexity to your space-complexity (e.g. with tabulation you have more liberty to throw away calculations, like using tabulation with Fib lets you use O(1) space, but memoization with Fib uses O(N) stack space). 详看

Dynamic programming and memoization: bottom-up vs top-down approaches

Tabulation vs Memoizatation - top-down(memorize)

def memorize_fib(n): # n为第几个Fibonacci数
memo = {1:1, 2:1}
if n in memo:
return memo[n]
else:
memo[n] = memorize_fib(n-1) + memorize_fib(n-2)
return memo[n]

print(memorize_fib(4))


• bottom up(tabulation)
def tabulation_fib(n):  # n为第几个Fibonacci数
fib = [1, 1, 2]
if n < 4:
return fib[n-1]
for k in range(3, n+1):
fib[2] = fib[0] + fib[1]
fib[0], fib[1] = fib[1], fib[2]
return fib[2]

print(tabulation_fib(4))


AC 代码(这里采用bottom up思想)

class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
fib = [1, 2, 3]
if n < 4:
return fib[n-1]
for k in range(3, n+1):
fib[2] = fib[0] + fib[1]              # 永远只存3个元素，save space
fib[0], fib[1] = fib[1], fib[2]
return fib[2]

• Complexity Analysis
- Time complexity : O(n)

- Space complexity : O(1). Constant space is used.


另外还有一个公式法：

class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
import math
sqrt5 = math.sqrt(5)
fibn = pow((1 + sqrt5) / 2, n+1) - pow((1 - sqrt5) / 2, n+1)
return int(float(fibn/sqrt5))

• Complexity Analysis
- Time complexity : O(lg(n)). pow method takes log(n) time.

- Space complexity : O(1). Constant space is used.