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

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

これは、 2番目の星と棒の定理のように聞こえます。

自然数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 3

それは数学の問題のようなものです。
k-1|sとnOsがあるとします。|は、それらのOをk個のパーティションに分割します。たとえば、k=3およびn=8の場合、次のように分割できます。

O O O | O | O O O O

最初のパーティションx1には3つのOがあり、2番目のパーティションx2には1つのOがあり、x3には4つのOがあります。つまり、3 + 1 + 4 = 8です。したがって、方程式の数は|sとOsの組み合わせの数です。 C（k + n-1、n）。