在整数中查找不同方程数的最快方法是什么？

Question

等式看起来像：

x1 x2 x3 x4 ... xk = n

和（ 0＆lt; = n＆lt; = 1000，0＆lt; k＆lt; = 1000 ）

示例：

n=3 and k=2
3+0=3 2+1=3
0+3=3 1+2=3
output: 4 // count of equations

我什么都没想到，即使是最糟糕的100循环方法。

Answer 1

n = 0 -> 1
k = 1 -> 1
k = 2 -> n + 1
k > 2 -> func(n, k - 1) + func(n - 1, k - 1) + .... + func(0, k - 1)
      // 0 + ...          1 + ...                     n + 0 + ... + 0

因此，递归地做....

int func(int n, int k) {
    assert (n >= 0);
    assert (k > 0);
    if (n == 0 || k == 1) {
        return 1;
    }
    else if (k == 2) {
        return n + 1;
    }
    else {
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            sum += func(i, k - 1);
        }
        return sum;
    }
}

消除冗余计算

int result[NMAX + 1][KMAX + 1] = {0};
int func(int n, int k) {
    assert (n >= 0);
    assert (k > 0);
    if (n == 0 || k == 1) {
        return 1;
    }
    else if (k == 2) {
        return n + 1;
    }
    else if (result[n][k] != 0) {
        return result[n][k];
    }
    else {
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            sum += func(i, k - 1);
        }
        result[n][k] = sum;
        return sum;
    }
}

Answer 2

这听起来像第二颗恒星和栏定理。

对于任何一对自然数 k 和 n ，非阴性整数的独特 k - tus n 的数量em> n 由二项式系数（ ^{k n -1} _n ）...

（我已经交换了 n 和 k 在Wikipedia中的描述中以匹配您的问题。）

所以，在您给您给n = 3和k = 2的示例中，答案是（ ^{2 3-1} ₃ ）=（ ⁴ ₃ ）= 4！/（（4-3）！＆Times; 3！）= 4。

因此，如果预先缓存阶乘值，则应该能够为 k 和 n 的任何值快速进行计算。。

Answer 3

它更像是一个数学问题。
假设您有K-1 | S和N OS。| s将这些OS分为K分区。例如，如果k = 3和n = 8，则可以像这样

分开

O O O | O | O O O O

第一个分区X1具有3个OS，第二个分区X2具有1 O，而X3具有4个OS，即3 1 4 = 8。因此，方程计数是| s和os的组合数，或C（k n -1，n）。