Link: https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers/description/
## 思路
需要注意的是它需要the number of ways ```n``` can be expressed as the sum of the xth power of **unique** positive integers
所以4 = 1+1+1+1 是不可能发生的 只能用一个1
而且不讲求顺序 所以backtracking也不可以
如果第11行改成```for i in range(power, n+1)``` 那么就是允许一个组合里可以有很多同一个数字的可能性 如果反过来 才是不允许
## Code

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        powers = []
        for i in range(1, 301):
            if pow(i, x)>n: break
            powers.append(pow(i, x))
        
        dp = [0]*(n+1)
        dp[0] = 1
        for power in powers:
            for i in range(n, power-1, -1):
                dp[i] = (dp[i]+dp[i-power])%(1e9+7)
                dp[i] = int(dp[i])
        return dp[n]