2787. Ways to Express an Integer as Sum of Powers

link

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:

        MOD = 10 ** 9 + 7

        @cache
        def backtrack(s, current):
            if current < 0:
                return 0
            if current == 0:
                return 1

            val = pow(s, x, MOD)
            if val > current:
                return 0

            total = 0
            total += backtrack(s+1, current - val)
            total += backtrack(s+1, current)

            return total % MOD

        return backtrack(1, n)

TBD

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        dp = [0] * (n+1)
        mod = 10 ** 9 + 7

        dp[0] = 1

        for num in range(1, n+1):
            m = num**x
            for i in range(n, 0, -1):
                if i - m >= 0:
                    dp[i] += dp[i-m]
                    dp[i] %= mod

        return dp[n] % mod