class Solution {
public:
int numberOfWays(int n, int x) {
}
};
6922. 将一个数字表示成幂的和的方案数
给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。
由于答案可能非常大，请你将它对 109 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。
示例 1：
输入：n = 10, x = 2 输出：1 解释：我们可以将 n 表示为：n = 32 + 12 = 10 。 这是唯一将 10 表达成不同整数 2 次方之和的方案。
示例 2：
输入：n = 4, x = 1 输出：2 解释：我们可以将 n 按以下方案表示： - n = 41 = 4 。 - n = 31 + 11 = 4 。
提示：
1 <= n <= 3001 <= x <= 5原站题解
java 解法, 执行用时: 43 ms, 内存消耗: 41.7 MB, 提交时间: 2023-07-24 10:14:51
class Solution {
public static final int MOD = (int)(1e9 + 7);
public int numberOfWays(int n, int x) {
List<Integer> nums = new ArrayList<>();// 所有可能的x的幂
int res = 0;
for (int i = 1; Math.pow(i, x) <= n; i++){
nums.add((int)Math.pow(i, x));
}
// 01背包问题，不可重复
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 0; i < nums.size(); i++){
for (int j = n; j >= nums.get(i); j--){
dp[j] = (dp[j] + dp[j - nums.get(i)]) % MOD;
}
}
return dp[n];
}
}
python3 解法, 执行用时: 3960 ms, 内存消耗: 668.2 MB, 提交时间: 2023-07-24 10:14:04
class Solution:
# 方法一：记忆化搜索
def numberOfWays(self, n: int, x: int) -> int:
mod = 10 ** 9 + 7
@cache
# 函数dfs(num, target)的解释:
# num:当前遍历到的数
# target:期望组合成的数
# dfs()的意义：找到以整数num开始的，能形成幂和的方案数
# 以例题1:"输入：n = 10, x = 2" 为例，可以由下面步骤得来：
# 1. 从整数1，2，3中依次寻找， 从1开始
# 2-1. 如果到达1，如果选择了1，那方案数为dfs(0, 10 - 1 ** 2)，即dfs(0, 9)
# 2-2. 如果到达1，但是没有选择1，那方案数为dfs(0, 10)，即到达0，目的仍然为10的方案数
# 3. 所以到达1的方案数dfs(1, 10) = dfs(0, 10 - 1 ** 2) + dfs(0, 10)
def dfs(num, target):
# 如果target为0，说明已经组合成功，则返回1（种情况）
if target == 0:
return 1
# 如果当前数的x幂已经超过target了，说明后面已经没必要进行下去（因为是正整数）
if num ** x > target:
return 0
# 选择了当前的整数的方案数
res = dfs(num+1, target- num ** x) % mod
# 加上不选择当前的整数的方案数
res = (res + dfs(num+1, target)) % mod
return res
# dfs(1, n)意思是从整数1开始找，目标是n的方案数
return dfs(1, n)
# 方法二：二维DP/背包问题，时间O(nlogn)，空间O(nlogn)
def numberOfWays_2(self, n: int, x: int) -> int:
mod = 10 ** 9 + 7
# 此处用n+1的原因是防止精度丢失，比如n=64, x = 3，math.pow(64, 3) = 2.999999，会导致max_num = 2
max_num = int(math.pow(n+1, 1/x))
# DP[num][target]意义为：方案选到整数num时，能够组成幂和为target的方案数
dp = [[0] * (n+1) for _ in range(max_num+1)]
# 初始化：方案选为0时，幂和为0的方案数为1
dp[0][0] = 1
for num in range(1, max_num+1):
for target in range(n+1):
# 不选num数时
dp[num][target] = dp[num-1][target]
# 选num数时，需要保证target-num ** x >=0，能才选
if target >= num ** x:
dp[num][target] = (dp[num][target] + dp[num-1][target-num ** x]) % mod
return dp[max_num][n]
# 方法三：优化后的一维DP/背包问题, 时间O(nlogn)，空间O(logn)
def numberOfWays_3(self, n: int, x: int) -> int:
mod = 10 ** 9 + 7
max_num = int(math.pow(n+1, 1/x))
dp = [0] * (n+1)
dp[0] = 1
for num in range(1, max_num+1):
# 此处为倒序
# 以上述二维dp的转移方程为例：dp[num][target] = dp[num-1][target] + dp[num][target-num**x]
# 可以知道当前的状态dp[num][target]只与上一行有关，而且只与上一行的并且列数小于等于当前列的状态有关
# 请大家画个矩阵出来，就可以容易的看出，只有使用倒序，在更新最新一行时，不会覆盖对后面有意义的上一行的数据
for target in range(n, -1, -1):
if target >= num ** x:
dp[target] = (dp[target] + dp[target - num ** x] ) % mod
return dp[n]
golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2023-07-24 10:13:05
func numberOfWays(n, x int) int {
f := make([]int, n+1)
f[0] = 1
for i := 1; pow(i, x) <= n; i++ {
v := pow(i, x)
for s := n; s >= v; s-- {
f[s] += f[s-v]
}
}
return f[n] % (1e9 + 7)
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x
}
x = x * x
}
return res
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-07-24 10:12:24
'''
0-1背包问题
n看做背包容量, ni^x 看做物品，装满背包有几种物品组合方法
'''
MX_N, MX_X = 300, 5
f = [[1] + [0] * MX_N for _ in range(MX_X)] # 5行301列的二维矩阵
for x in range(MX_X):
for i in count(1):
v = i ** (x + 1)
if v > MX_N: break
for s in range(MX_N, v - 1, -1):
f[x][s] += f[x][s - v]
class Solution:
def numberOfWays(self, n: int, x: int) -> int:
return f[x - 1][n] % (10 ** 9 + 7)