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

Question

方程看起来像这样：

x1 + x2 + x3 + x4 + ... + xk = n

和 ( 0 <= n <= 1000, 0 < k <=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

这听起来像第二个星条定理。

对于任何一对自然数k和n ，其和为n的非负整数的不同k元组的数量由二项式系数 ( ^{k + n - 1} _n ) 给出...

（我已经从维基百科的描述中交换了n和k以匹配您的问题。）

因此，在您给出的 n=3 和 k=2 的示例中，答案是( ^{2 + 3 - 1} ₃ ) = ( ⁴ ₃ ) = 4！/ ((4 - 3)! × 3!) = 4。

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

Answer 2

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 3

这更像是一道数学题。
假设您有 k-1 |s 和 n 个 Os。|s 将这些 Os 分成 k 个分区。例如，如果 k = 3 和 n = 8，它可能会像这样拆分

O O O | O | O O O O

第一个分区x1有3个O，第二个分区x2有1个O，x3有4个O，即3 + 1 + 4 = 8。所以方程的个数就是|s和O的组合数，或者C(k + n - 1, n)。