4

私は動的プログラミングの問題を解決しようとしていますが、問題の一部には、合計すると数値「n」になる一連の「p」数値の順列の数を見つけることが含まれます。p 個の数値のセット内の各数値は、0 から n までの範囲である必要があります。

たとえば、n = 4 で p = 3 の場合、次の 12 の順列があります。

{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}

私はこのDPアプローチから始めました。

n(i,j) represents number of ways of representing n using i,j in p positions

私の基本ケースは

n(i,0) = n(0,i) = p

(たとえば、p=3 桁の n(4,0) は 3 であり、{4,0,0},{0,4,0},0,0,4}

再帰的なケース

n(i,j) = n(i,j-1)*n(i-1,j)

(例: n(1,2) = n(1,1) * n(0,2) n(1,0) * n(0,1) * 2 に再帰)

上記のアプローチでは正しい答えが得られないため、正しい方向に進んでいるかどうかはわかりません。私を正しい方向に導いてください。

4

1 に答える 1

7

私のコメントに反して、セットの数とそれらのセットの順列を同時に数えると、この問題は実際には解決しやすくなります。

各セットを実際に生成する代わりにカウントするだけでよい場合は、いくつかの単純な組み合わせ論で直接行うことができます。例を修正して、ボールp = 3, n = 5があると想像してみましょう。n = 5

o o o o o

3ここでの質問は次のようになります。各グループがボールを持つことができるグループにボールを分割するには、いくつの方法があり[0, 5]ますか? p - 1 = 25 つのボールすべての前、5 つのボールすべての後、任意の 2 つのボールの間など、どこにでも個別に配置できるスティックがあると想像してください。例えば：

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

質問がどのように同等であるかに注意してください。とにかく、それらの棒を入れることができます。また、nボールをpセットに分割することもできます。p - 1数字を生成するのに棒だけが必要であることに注意してくださいp(最初の棒の前のすべてのボールは最初のグループであり、最後の棒の後のすべてのボールは最後のグループであり、2 つの棒の間のすべてのボールは他のグループです)。

nでは、私たちの質問は、ボールとp - 1スティックを配置する方法はいくつあるでしょうか? スロットがあると考えることができ、ボールn + (p - 1)のスポットを選んでいるだけnです.残りはスティックが行くところです. このように考えると、組み合わせ論の基本的な公式を適用することができます (公理的な和の法則と積の法則を使用して証明されています...証明を見たことがあるかどうかはわかりません):

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

したがって、この例では、7! / 5! / 2! = 21です。そして、あなたの例ではそれが6! / 4! / 2! = 15. いくつかの順列を見逃しました (たとえば、{0, 3, 1})。

これは、単純な再帰方程式によって DP で解決することもできます。基本的

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

の値のいくつかをメモしますf。アイデアは、セットの最初のメンバーの値を選択しS、次の再帰呼び出しで次のメンバーを選択するというものSです。f(0, p) = 1基本ケースはおそらくandのようなものでf(n, 0) = 0、それ以外の場合は再帰ケースを使用できます。セット自体を実際に必要としない場合でも、閉じた形式の方が明らかにパフォーマンスが優れています。

于 2013-06-29T01:30:39.580 に答える