试图找出幂和问题解决方案的复杂性

Question

问题->找到整数可以表示为唯一自然数的n次方之和的方法

示例->x=100，n=2

输出->100=(10^2)或(6^2+8^2)或者(1^2+3^2+4^2+5^2+7^2)因此总共有3种可能性

我的代码

private static int Helper(int x,int n,int current){   
if(x==0)
return 1;
int answer = 0;
int power = (int)Math.pow(current,n);
if(power<=x){
//Including current
answer += Helper(x-power,n,current+1);
//Excluding current
answer += Helper(x,n,current+1);
}
return answer;
}
public static int findCount(int x, int n) {
return Helper(x,n,1);
}

我的方法-我试图通过包括当前自然数并排除它来找到解决方案。对于上面的例子，答案可以包含1(1^2+3^2+4^2+5^2+7^2)或不包含(10^2)

我正试图分析我所写代码的时间复杂性。但我既不能写递归关系，也不能用任何模式构造递归树。有人能帮我吗？

Answer 1

您的想法是使用递归回溯，而不使用记忆(动态编程的一个概念)。因此，您可能会重复计算同一个子问题，即在同一个x、n和current上多次调用helper方法。这可能导致指数运行时间。

更好的方法是使用如下所示的动态编程。(添加了一些评论)。

这里有几个注意事项：

1. 我假设在计算x^n时不会有任何整数溢出
2. powerToN方法可以使用二进制搜索的概念进行优化，以实现O(logN)时间。(x^n=x^(n/2)*x^(n/2))。但在这个问题中，n不会很大，所以这无关紧要
3. 运行时是O(X*X^(1/n))，使用这种动态编程解决方案可以非常直接地分析运行时和空间复杂性

import java.util.ArrayList;
import java.util.List;
public class PowerSum
{
public int findPowerSumWaysDp(int x, int n) {
//O(X ^ (1 / n))
List<Integer> candidates = new ArrayList<>();
for(int i = 1; i <= x; i++) {
int v = powerToN(i, n);
if(v <= x) candidates.add(v);
else break;
}
//find the number of ways to sum to x, in each way we can only use the same number once
int k = candidates.size();
if(k == 0) return 0;
//dp[i][j]: the number of ways to sum to i with the first j numbers in candidates
int[][] dp = new int[x + 1][k + 1];
//for sum 0, there is always 1 way, that is to not pick any number.
for(int i = 0; i <= k; i++) {
dp[0][i] = 1;
}
for(int i = 1; i <= k; i++) {
for(int j = 1; j <= x; j++) {
//if we can use the current number, use it
if(j >= candidates.get(i - 1)) {
dp[j][i] = dp[j][i] + dp[j - candidates.get(i - 1)][i - 1];
}
//we can always choose not to use the current number
dp[j][i] = dp[j][i] + dp[j][i - 1];
}
}
return dp[x][k];
}
private int powerToN(int x, int n) {
int v = 1;
for(int i = 1; i <= n; i++) {
v *= x;
}
return v;
}
public static void main(String[] args) {
PowerSum powerSum = new PowerSum();
int x = 100;
int n = 2;
System.out.println(powerSum.findPowerSumWaysDp(x, n));
}
}