Googleインタビューパズル

Question

n個のサイコロを与えられた場合、それぞれのa面と合計bは、合計bが得られるウェイ数を返します。どのようにして時間の複雑さと空間の複雑さを減らすことができますか？ これはGoogleのインタビューで尋ねられました。私は答えが不明です。

Answer 1

（比A> = B-Nする）十分な大きさであると仮定すると、これは 'N' 子供の中 'のB' キャンディーを配布する一般的な問題である

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

まで沸騰。あなたは0が直面しないようにしたい場合は K-、とても

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

Z1 + Z2 + ... ZK =の一般解nが C（N + K-1であることを確認するために簡単なはず死にますいくつかのdownvotesをreciving後1）

EDIT：

たちは

DPの問題としてそれを定式化することができ、我々は '' すなわちBN> A、 上の制限を持っていると仮定すると、

その後、我々は次のような関係

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 

と答えを評価することができます[n]はDPである必要があり、[B] ストレージであれば次数n * b、およびランタイムOの（N * B * A）

Answer 2

これはnの正の整数の合計としてbを書き込む方法の数を見つけるよう求めています。答えはcompositionsのbにnの部分の番号です。これは(b-1 choose n-1)です。

ここで、部品のサイズがaに制限されているという制約を考慮すると、問題はもう少し面白くなります。これにはgenerating functionsを使用することをおすすめします。答えは製品(x+x^2+...+x^a)^nの係数x^bになります。どうして？各ダイ（ダイスの単数形）については、1とaの間の数値があり、これは指数がxで表されています。 nの各単語から1つずつx^iを取得すると、これは数字のiと同じです。指数の合計は、あなたの後の合計、つまりbでなければなりません。

は、私たちも述べmultinomial theoremを使用して問題を少し簡略化することができます。すべてのki >= 0

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

を。だから、答えはいくつかの方法が

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

Answer 3

であるということである私は、それぞれの値の可能な組み合わせの数をカウント配列hits[max + 1]を持っているでしょう。 maxはn * aであり、もちろんhits[0]~hits[n - 1]は空のままです。

愚かなやり方は、ループのためにn（各ダイに1つ）を実行し、ダイスの現在の合計についてhitsにヒットを登録することです。

以下ダム方法は、私は各順序付けシャッフルするための組み合わせの数を書き出す組合せ論のビットを使用することである。

1111 1つの組合せがある（合計= 4）
あります1112の4組み合わせ（和= 5）
1113 4組み合わせ（合計= 6）
...
1123 4 * 3月2日の組み合わせ（和= 7）
がある...
があります 4 * 3 * 2 comがあります1234年のbinations（合計= 10）
...
あなたはダムソリューションよりも、forループにあまり時間を費やす必要がaaaa（合計= n * a）

の1つの組み合わせがあります。
ダムメソッドでヒットするのではなく、繰り返しごとに多くのヒットが得られます。

これらのforループは、（1,2,3,4、...、a）を超える（n - 1）パーティションの区切りを移動するだけです。 区切りは同じ場所にすることができます（例：ケース1111の場合はすべて1と2の間です）。ただし、1未満またはそれ以下の間隔を持たないようにしてください。a