50. Pow(x, n)

Loading...LeetCode

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

Bottom-up DP (MLE)

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]
            

Top-down DP

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)