```
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
mem = {}
rt = self.do(x, abs(n), mem)
if n < 0:
return float(1)/rt
return rt
def do(self, x, n, mem):
if n == 0:
return 1
if n == 1:
return x
if n/2 not in mem:
mem[n/2] = self.do(x, n/2, mem)
if n-(n/2) not in mem:
mem[n-(n/2)] = self.do(x, n-(n/2), mem)
return mem[n/2] * mem[n-(n/2)]
```