algorithm - Google インタビュー パズル

Question

n 個のサイコロを指定すると、それぞれの 'a' 側と合計 b は、合計 b を取得できる方法の数を返します。時間の複雑さと空間の複雑さをどのように軽減できますか? これは Google のインタビューで尋ねられたもので、答えがわかりません。

Answer 1

これは、正の整数bの和として書き方の数を求めています。n答えは を部分に合成した数で、これはです。bn(b-1 choose n-1)

ここで、パーツのサイズが に制限されているという制約を考慮するaと、問題はもう少し興味深いものになります。これには生成関数を使用することをお勧めします。答えはx^b積の の係数になります(x+x^2+...+x^a)^n。なんで？各サイコロ (サイコロの単数形) には、 と の間の数字が1ありa、これは の指数で表されるためですx。x^i各用語から1 つを取ると、これはそのサイコロに出てくるn数字に相当します。i指数の合計は、求める合計、つまり でなければなりませんb。

次の多項式定理を使用して、問題を少し単純化することもできます。

(x + x^2 + ... + x^a)^n = sum_{k1+k2+...+ka=n} (n multichoose k1,k2,...,ka) x^{k1+2*k2+...+a*ka}

すべての場所ki >= 0。答えは、方法の数は

sum_{k1+k2+...+ka=n & k1+2*k2+...+a*ka=b} (n multichoose k1,k2,...,ka)

Answer 2

hits[max + 1]各値の可能な組み合わせの数をカウント する配列があります。maxisn * aとhits[0]tohits[n - 1]は空のままです。

愚かな方法はn、for ループ (ダイスごとに 1 つ) を実行hitsし、ダイスの現在の合計にヒットを登録することです。

それほどばかげていない方法は、組み合わせ論を少し使用することです。ここでは、順序付けられたシャッフル ごとに組み合わせの数を書き出します。

1111 の組み合わせが 1 つある (合計 = 4)
1112 の組み合わせが 4 つある (合計 = 5)
1113 の組み合わせが 4 つある (合計 = 6)
...
1123 の組み合わせが 4 * 3 / 2 ある (合計 = 7) )
...
1234 (合計 = 10) の組み合わせが 4 * 3 * 2 ある
... (合計 = )
の組み合わせが 1 つあるaaaan * a

愚かなソリューションよりも for ループに費やす時間がはるかに少なくて済みます。
愚かな方法では1回のヒットだけではなく、反復ごとに多くのヒットが得られます。

これらの for ループは、(n - 1) パーティション分離を (1, 2, 3, 4, ..., a) に移動するだけです。分離は同じ場所にあってもかまいません (例: 1111 の場合、それらはすべて 1 と 2 の間にあります) a。

Answer 3

a が十分に大きい (具体的には a>=bn) と仮定すると、これは次のように要約されます。

x1+x2+x3+...+xn=b

これは、「b」個のキャンディーを「n」人の子供に配布する際の典型的な問題です。直面したダイスが 0 になるのを避けたい場合は、簡単に確認できるはずです。

(y1+1)+(y2+1)...+(yn+1)=b
y1+y2+...+yn=b-n

z1+z2+...zk=n の一般解は C(n+k-1,k-1) です

いくつかの反対票を受け取った後の編集：

'a' に制限がある、つまり bn>a と仮定すると、それを DP 問題として定式化できます。

dp[k][j] is no. of ways to get a sum of j using dices 1 to k inclusive
dp[1][j] is 0 if j>a or j==0 else 1

次に、次の関係を評価することができます

from k = 2 to n
  from j = 1 to b
     from x = 1 to a
        dp[k][j] += dp[k-1][j-x] where x is from 1 to a at max and x<j

答えは dp[n][b] である必要があります。次数 n*b でランタイム O(n*b*a) の場合のストレージ