目标
给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。
由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。
示例 1：
输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。示例 2：
输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4^1 = 4 。
- n = 3^1 + 1^1 = 4 。说明：
- 1 <= n <= 300
- 1 <= x <= 5
思路
求正整数的 x 次幂之和为 n 的组合数，要求组合中的数字不能重复。
最大正整数 max = n^(1/x)，问题转换为使用 1^x, 2^x, ……, max^x 组成 n 的组合数。
恰好型 0-1 背包。
代码
/**
* @date 2025-08-12 9:08
*/
public class NumberOfWays2787 {
public int numberOfWays(int n, int x) {
int mod = 1000000007;
int max = (int) Math.ceil(Math.pow(n, 1.0 / x));
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= max; i++) {
int pow = (int) Math.pow(i, x);
for (int j = n; j >= pow; j--) {
dp[j] += dp[j - pow];
}
}
return (int)(dp[n] % mod);
}
}
性能
