Mid/SeniorDynamic Programming
Ways to Express an Integer as Sum of Powers
Given two positive integers n and x.
Return the number of ways n can be expressed as the sum of the x^th power of unique positive integers. In other words, return the number of sets of unique integers [n1, n2, ..., nk] where n = n1^x + n2^x + ... + nk^x.
Since the result can be very large, return it modulo 10^9 + 7.
For example, if n = 160 and x = 3, one way to express n is n = 2^3 + 3^3 + 5^3.
Example 1
Input
n = 10, x = 2Output
1We can express 10 only as 3^2 + 1^2 = 10 using unique positive integers.
Example 2
Input
n = 4, x = 1Output
2We can express 4 as either 4^1 or 3^1 + 1^1.
Constraints
- 1 <= n <= 300
- 1 <= x <= 5