プログラミングコンテストチャレンジブックを読んでいたら、初級編からいきなり分割数DPで躓いたので、理解するまでの過程をここで書き留めました。
自分なりに理解したDPの解釈から紹介していきます。
「n個の互いに区別できない商品を、m個以下に分割するパターンの総数を求めよ」という問題を考える。
これは言い換えると、整数nをm個以下の正整数の和で表す方法のうち、順序を区別しないものの個数を求める問題である。
例えば、n = 4、m = 3のとき、該当するような分割は
{1, 1, 2}, {1, 3}, {2, 2}, {4}
のような4組が見つかる。
順序を区別しないため、各分割を昇順に並べた数列とみなせば、「要素数がm以下で、総和がnとなる昇順の数列の個数」を求める問題と言い換えられる。
また、このような数列が一つ一つの方法となる。
ここで、dp[i][j]を「整数iをちょうどj個の正整数の和として表す方法の数」として表す。
dp[i][j]において考えられる方法の数列で、1を含むか含まないかで場合分けする。
まず、1を少なくとも1個含むような数列があるとすると、それは1を取り除くと、i-1をちょうどj-1項で表す分割となる。
次に、すべての項が2以上であるものを考えると、この場合各項から1を引くと、i-jをちょうどj項で表すような分割になる。
よって、dp[i][j] = dp[i-1][j-1] + dp[i-j][j]となる。
求めたいのはm個以下の分割数なので、最終的な答えは$\sum_{j=1}^mdp[n][j]$となる。
本の内容を理解したいので、ここからさらに本の内容について踏み込んでいきます。
答えは同じですが、DPの意味が変わってくるので、本の内容で理解したい人向けだと思います。
nのm分割$a_i$($\sum_{i=1}^{m}a_i=n$)は$(a_1, a_2, ..., a_m)$において考えます。
ただし、aは昇順であるものとします。先程の説明と少し違うことを行っています。
dp[i][j]をiをj個以下に分割する方法の数とする。（さっきの説明とは違うよ）
iのj分割を先頭が0かどうかで場合分けする。
$a_1=0$ならば、
$(a_1, ..., a_j)$から先頭を取り除いた$(a_2, ..., a_j)$のようなものはiをj-1個以下に分割する方法に対応する。
$a_1>0$ならば、
$(a_1-1, a_2-1, ..., a_j-1)$を考えると、これは各項から1を引いたのでi-jをj個以下に分割する方法に対応する。
これらによってdp[i][j] = dp[i-j][j] + dp[i][j-1]が成り立つ。
わかりにくかったら申し訳ないです。