MS での f2f インタビューでのインタビューからの質問:
の積分解の数を決定する
x1 + x2 + x3 + x4 + x5 = N
どこ0 <= xi <= N
したがって、基本的には、N の分割数を最大 5 つの部分で見つける必要があります。紙と鉛筆で解くことを想定しています。あまり進歩していませんが、これに対する解決策はありますか？
質問する
272 次
5 に答える
3
数値が厳密に > 0 であると仮定します。
整数セグメント[0, N]を考えます。問題は、それを正の長さの4つのセグメントに分割することです。隣接する数字の間に 4 つの分割ドットを配置することでそれを行うと想像してください。それを行う方法はいくつありますか？C(N-1, 4) .
現在、一部の数値は 0-s である可能性があります。kをゼロ以外の数とします。それぞれがC(N-1, k) 個の分割を持つため、C(5,k) 個の方法でそれらを選択できます。[0,5]範囲のすべてのkを累積すると、 Sum[ C(5,k) * C(n-1,k);が得られます。ｋ＝０～５］
于 2012-08-07T12:34:51.577 に答える
2
「組み合わせと繰り返し」のセクションを探してください。特定のケースは、そのセクションの下に図解付きで説明されています。
于 2012-08-07T13:10:28.467 に答える
2
于 2012-08-07T13:12:36.577 に答える
2
@Grigor Gevorgyanは確かに解決策を理解する正しい方法を提供します。
いつ考えよう
1 <= xi
これは正確に N ポイントを 5 つのセグメントに分割しています。N-1 の可能な場所 (隣接する数字の間) から 4 つの「分割ドット」を挿入することと同じです。したがって、答えは C(N-1,4) です。
じゃあいつ？
0 <= xi
?
X+5 点の解がある場合
1 <= xi
その答えはC(N-1,4)=C(X+5-1,4)=C(X+4,4)
次に、各セットから 1 つのポイントを削除するだけで、X ポイントの解が得られます。
0 <= xi
つまり、今の答えは正確に等しいC(X+4,4)
于 2012-08-07T13:04:52.170 に答える
1
ペンと紙の解決策が求められた場合は、組み合わせの解決策がより適切です。それはまた古典的な解決策です。これが動的計画法ソリューションです。
しましょうdp[i, N] = number of solutions of x1 + x2 + ... +xi = N。
取りましょうx1 + x2 = N：
解決策があります：
0 + N = N
1 + N - 1 = N
...
N + 0 = N
だからdp[2, N] = N + 1解決策。
取りましょうx1 + x2 + x3 = N：
解決策があります：
0 + (0 + N) = N
0 + (1 + N - 1) = N
...
0 + (N + 0) = N
...
これまでのところ解決策があることに注意してくださいN + 1。次に進む：
1 + (0 + N - 1) = N
1 + (1 + N - 2) = N
...
1 + (N - 1 + 0) = N
...
別の解決策があることに注意してくださいN。次に進む：
...
N - 1 + (0 + 1) = N
N - 1 + (1 + 0) = N
=> +2 solutions
N + (0 + 0) = N
=> +1 solution
だから私たちは持っていdp[3, N] = dp[2, N] + dp[2, N - 1] + dp[2, N - 2] + ... + dp[2, 0]ます。
また、それに注意してくださいdp[k, 0] = 1
行列の各行にはN総和が必要なので、計算の複雑さdp[k, N]は ですO(k*N)。これは、組合せ解に必要なのと同じです。
各行の複雑さを維持するにはO(N)、 を格納しs[i] = sum of the first i elements on the previous rowます。メモリ使用量も削減できますO(N)。
于 2012-08-07T13:20:26.390 に答える