<p>Given two <strong>positive</strong> integers <code>n</code> and <code>x</code>.</p>

<p>Return <em>the number of ways </em><code>n</code><em> can be expressed as the sum of the </em><code>x<sup>th</sup></code><em> power of <strong>unique</strong> positive integers, in other words, the number of sets of unique integers </em><code>[n<sub>1</sub>, n<sub>2</sub>, ..., n<sub>k</sub>]</code><em> where </em><code>n = n<sub>1</sub><sup>x</sup> + n<sub>2</sub><sup>x</sup> + ... + n<sub>k</sub><sup>x</sup></code><em>.</em></p>

<p>Since the result can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>For example, if <code>n = 160</code> and <code>x = 3</code>, one way to express <code>n</code> is <code>n = 2<sup>3</sup> + 3<sup>3</sup> + 5<sup>3</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10, x = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can express n as the following: n = 3<sup>2</sup> + 1<sup>2</sup> = 10.
It can be shown that it is the only way to express 10 as the sum of the 2<sup>nd</sup> power of unique integers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, x = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can express n in the following ways:
- n = 4<sup>1</sup> = 4.
- n = 3<sup>1</sup> + 1<sup>1</sup> = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>1 &lt;= x &lt;= 5</code></li>
</ul>

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        #assume you have to make n target
        # and you can have a list of  coins that increase
        # from 1 to z where z <= n.
        coins = []
        memo = dict()
        for i in range(1,n+1):
            if i**x <= n:
                coins.append(i**x)
            else:
                break
        #print(coins)
        mod = 10 ** 9 + 7
        
        def dfs(idx,target):
            if target == 0:
                return 1
            if idx == 0:
                if coins[idx] == target:
                    return 1
                return 0
            """
            if target < 0:
                return 0
            if idx < 0:
                return 0
            """
            if (idx,target) in memo:
                return memo[(idx,target)]
            take,not_take = 0,0

            if target >= coins[idx] :
                take = dfs(idx-1,target-coins[idx])
            
            not_take = dfs(idx-1,target)
            memo[(idx,target)] = take+not_take
            return memo[(idx,target)] % mod
        return dfs(len(coins)-1,n)
        """
        dp = [[-1 for _ in range(len(coins))] for _ in range(n+1)]
        
        # noe take a look at the base cases
        # bcase1 - if target is Zerpo, return 1
        for i in range(len(coins)):
            dp[0][i] = 1
        
        for i in range(n+1):
            for j in range(len(coins)):
                if coins[j] == i:
                    dp[i][j] = 1
        for i in range(1,n+1):
            for j in range(len(coins)):
                take = dp[i-1][i-coins[j]] if coins[j] < i else 0
                not_take = dp[i-1][i]
                dp[i][j] = take + not_take
        return dp[n][len(coins)-1]
        #print(dp)
        """

        
        






        
254831