分割数を考える

『プログラミングコンテストチャレンジブック』で挑戦した問題。

n個の互いに区別できない商品を、m個以下に分割するパターンの総数を求めよ。

一般に、m=nのとき、このパターン数をnの分割数と呼ぶらしい。

悩んで、悩んで2つ日目に分かった。（解説が天才的すぎて凡人の僕にはちょっと理解できません。。）

以下、凡人でも分かりそうな解説。

まず、dp[i][j]を整数jをi個以下に分割するパターン数とする。

jをi個以下に分割するパターンは、jをi-1個以下に分割するパターンとjをi個に分割するパターンの和である。ここで、前者の「jをi-1個に分割するパターン」はdp[i-1][j]と書ける。

次に後者。「jをi個に分割するパターン」は、予めi個を1個ずつi個の集合に割り当てて、残ったj-i個をこの集合に割り当てるパターンを考えればいいと分かる。

ちょっと、ややこしいので例題を。

10個を4個に分けるパターンは、まず集合が4ついるので、それぞれの集合に1個ずつ割り当てる。

1, 1, 1, 1

あとは、残った6個をこの4つの集合に割り振るパターン数を考えればよい。

例えば、

6, 0, 0, 0

1, 1, 1, 3

2, 2, 0, 2

などが考えられる。

これを、予め作っておいた集合

1, 1, 1, 1に加えれば4つに分割するパターンが出来ることがわかる。よって、「jをi個に分割するパターン」は、dp[i][j-i]と書ける。

以上の議論から、

dp[i][j] = dp[i-1][j] + dp[i][j-i]

という漸化式が得られる。これはDPを使えば、O(n*m)で解けます。

ソースは、・・・・・

ソースを見たい人は、この本を買おう！（笑）