有一个关于n次方和的算法问题here，我试图使用递归来解决这个问题，但在我在线检查解决方案之前，递归不起作用，我得到了这个：
public class Main {
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int x = s.nextInt(), n = s.nextInt();
int end = (int)Math.pow(x, 1.0/n);
System.out.print(sumOfPower(x, n, end));
}
static int sumOfPower(int number, int power, int end) {
int[] temp = new int[number + 1];
temp[0] = 1;
for(int i = 1; i <= end; i++) {
int value = (int)Math.pow(i, power);
for(int j = number; j > value - 1; j--) {
temp[j] += temp[j-value];
}
}
return temp[number];
}
我试图通过记录每个循环的结果来研究代码，因此
sumOfPower方法现在看起来如下：static int sumOfPower(int number, int power, int end) {
int[] temp = new int[number + 1];
temp[0] = 1;
for(int i = 1; i <= end; i++) {
int value = (int)Math.pow(i, power);
for(int j = number; j > value - 1; j--) {
System.out.println( "j:"+j+"\tj-value:"+(j-value)+ "\ttemp[j]:" + temp[j] + "\ttemp[j-value]:" + temp[j-value] );
temp[j] += temp[j-value];
System.out.println(i + ": " + Arrays.toString(temp));
}
}
return temp[number];
}
我了解循环和动态编程逻辑在某种程度上是如何使用
x=10和n=2日志工作的。日志看起来像：10
2
j:10 j-value:9 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:9 j-value:8 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:8 j-value:7 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:7 j-value:6 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:6 j-value:5 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:5 j-value:4 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:4 j-value:3 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:3 j-value:2 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:2 j-value:1 temp[j]:0 temp[j-value]:0
1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:1 j-value:0 temp[j]:0 temp[j-value]:1
1: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:10 j-value:6 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:9 j-value:5 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:8 j-value:4 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:7 j-value:3 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:6 j-value:2 temp[j]:0 temp[j-value]:0
2: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
j:5 j-value:1 temp[j]:0 temp[j-value]:1
2: [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
j:4 j-value:0 temp[j]:0 temp[j-value]:1
2: [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]
j:10 j-value:1 temp[j]:0 temp[j-value]:1
3: [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1]
j:9 j-value:0 temp[j]:0 temp[j-value]:1
3: [1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1]
我现在需要知道的是这背后的数学逻辑，我怎么知道在循环之后
temp['number']是可以用唯一自然数的x幂和来表示的nth方法的总数。任何帮助都是非常感谢的。 最佳答案
让我们从问题的抽象模型开始，给出一个DAGdirected acyclic graph，从一个节点到另一个节点有多少种旅行方式？
让我们调用函数来回答这个问题f(start, end)
我们很容易看到
f(start, end) = sum f(x , end) with x are the neighbours of start
对于基本情况
f(end, end) = 1（有一种方法可以从端到端移动，因为这个图没有循环）因为这是一个DAG，所以上面的函数会收敛。类似地，您可以看到相同的模型可以应用于此问题。
假设我们需要用x作为初始值来计算
f(X, 0)，我们可以看到从x值，我们可以得到所有的值X - y，用y是n次方数。所以
f(X, 0) = sum f(X - y, 0) with y is all Nth power number less than or equal X
f(0,0) = 1
在您给出的代码中，
temp正在存储来自f的f(0, 0) to f(value, 0)的答案。所以，为什么这是一个达格？因为n次方的值是正的，所以我们不可能回到以前的状态。
关于java - 求和算法的功效，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47791542/