java - 求和算法的幂

Question

有个算法题here关于 n 次幂的总和，我尝试使用递归来解决问题，但在我在线检查解决方案之前它不起作用，我得到了这个:

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 可以表示为唯一自然数的 n 次 次幂之和。非常感谢任何帮助。

Answer 1

让我们从问题的抽象模型开始，给出一个 DAG directed acyclic graph , 从一个节点到另一个节点有多少种方式？

让我们调用函数来回答这个问题是f(start, end)

我们很容易看出

f(start, end) = sum f(x , end) with x are the neighbours of start

对于基本案例 f(end, end) = 1 (有一种从头到尾的方式，因为这个图没有循环)。而且，由于这是一个 DAG，所以上述函数会收敛。

类似地，你可以看到同样的模型可以应用到这个问题上。

假设我们需要计算 f(X, 0)其中X是初始值，我们可以看到从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) .

那么，为什么这是 DAG？因为 N 次方的值为正，所以我们无法回到之前的状态。