Ways to Express an Integer as Sum of Powers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        dp = [1] + [0] * n
        a = 1
        mod = 10**9 + 7
        while (v := pow(a, x)) <= n:
            for i in range(n, v - 1, -1):
                dp[i] = (dp[i] + dp[i - v]) % mod
            a += 1
        return dp[n]