[LeetCode 2787] Ways to Express an Integer as Sum of Powers

문제 바로가기

Description

---

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, the number of sets of unique integers [n_1, n_2, ..., n_k] where n = n_1^x + n_2^x + ... + n_k^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 = 2
• Output: 1
• Explanation:
  • We can express n as the following: n = 3^2 + 1^2 = 10.
  • It can be shown that it is the only way to express 10 as the sum of the 2^nd power of unique integers.

Example 2

---

• Input: n = 4, x = 1
• Output: 2
• Explanation:
  • We can express n in the following ways:
  • n = 4^1 = 4.
  • n = 3^1 + 1^1 = 4.

Constraints

---

• 1 <= n <= 300
• 1 <= x <= 5

Hint

---

Hint 1

  You can use dynamic programming, where dp[k][j] represents the number of ways to express k as the sum of the x-th power of unique positive integers such that the biggest possible number we use is j.
	

Hint 2

  To calculate dp[k][j], you can iterate over the numbers smaller than j and try to use each one as a power of x to make our sum k.
	

Code

---

내 제출

---

class Solution {
    public int numberOfWays(int n, int x) {
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[n + 1][n + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            long k = (long) Math.pow(i, x);
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                if (k <= j) {
                    f[i][j] = (f[i][j] + f[i - 1][j - (int) k]) % mod;
                }
            }
        }
        return f[n][n];
    }
}

Runtime	Memory
62 ms	44.9 MB

다른 풀이

---

class Solution {
    public int numberOfWays(int n, int x) {
        int mod = 1_000_000_007;
     int[] dp=new int[n+1];
     dp[0]=1;
     for(int i=1;(int)Math.pow(i,x)<=n;i++)
     {
        int curr=(int)Math.pow(i,x);
        for(int num=n;num-curr>=0;num--)
        {
            dp[num]=(dp[num]+dp[num-curr])%mod;
        }
     }
     return dp[n];
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2700-2799/2787.Ways%20to%20Express%20an%20Integer%20as%20Sum%20of%20Powers/Solution.java