# 50. Pow(x, n)

{% embed url="<https://leetcode.com/problems/powx-n/>" %}

第一眼觉得就是很典型可以`bottom-up`的`DP`，写出来发现MLE，的确n大了就很消耗空间。改成`Top-down`应该可以省去一些exp值的计算，试了下。

{% tabs %}
{% tab title="Bottom-up DP (MLE)" %}

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        nv = abs(n)
        dp = [1 for t in range(nv+1)]
        
        dp[1] = x
        for i in range(2, nv+1):
            dp[i] = dp[i//2]*dp[i//2]*dp[i%2]
        
        return dp[-1] if n > 0 else 1.0/dp[-1]
            
```

{% endtab %}

{% tab title="Top-down DP" %}

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        nv, dp = abs(n), dict()
        
        def exp(x, n):
            if n in dp: return dp[n]
            if n == 1: return x
            dp[n] = exp(x, n//2) * exp(x, n-n//2)
            return dp[n]
        
        return exp(x, nv) if n>0 else 1.0/exp(x, nv)
```

{% endtab %}
{% endtabs %}
