読者です 読者をやめる 読者になる 読者になる

重複組み合わせの動的計画法での解法

蟻本で解説がよくわからなかったのでメモ

問題はn種類の品物があり、i番目の品物はa[i]個(配列)ある。同じ種類の品物は区別できない。これらの品物からm個選ぶときの組み合わせの総数を求めろ。

dp[i+1][j]をi番目までの品物からj個選ぶ組み合わせの総数としてdp[n][m]に解が入る。
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]]が成り立つのがこれが成り立つ式の変形がよく分からなかったので個人的な解釈を示す。
問題の一例として具体例としてA,B,Cの品物がそれぞれ3,2,1個あり3個選択する場合を考える。 まずdp[i+1][j-1] + dp[i][j]は選ぶ個数を減らしたものと、選ぶ種類を減らしたものの和である。A,B,Cから3個選択する場合なら、
A,B,Cから2個選択する数とA,Bから3個選択する数との和である。
A,B,Cから2個選択する場合の数はAA,AB,BB,AC,BCである。
同様にA,Bから3個選択する場合の数はAAA,AAB,ABBである。
A,B,Cから3個選択する場合の数はAAC,ABC,BBC,(AAA,AAB,ABB)である。
カッコの中で囲った場合の数は、A,Bから3個選択する場合の数と同様である。それ以外の場合の数はA,B,Cから2個選択する場合の数の語尾にCを加えたものである。
よってdp[i+1][j-1]は語尾を加えて追加する場合の数、dp[i][j]は変化なしに場合の数に加える数だということがわかる。 しかしAC,BCの後ろにCがついた場合の数は、Cの数が一つなので存在できないため、dp[i+1][j-1] + dp[i][j]だと場合の数が大きくなる。
ここで減算分を考える。
上記の場合だとACCとBCCの分を消す必要がある。結論から言うと前述してあるとおり、dp[i][j-1-a[i]]が必要ない数である。
i-1番目の数を加えるということは、i番目の荷物が含まれていない数ということである。つまりj-1はa[i]が1だったら加わり得る事のできる数である。
上記の例だとA,B,Cから2個選択する場合の数はAA,AB,BB,AC,BCだが、この中のAA,AB,BBはA,Bから2個選択する数である。
しかしa[i] = 1であれば j-2の数は加えることができない。 A,Bから1個選択する場合の数はA,Bであり、ACC,BCCは除外する数である。
そのためdp[i][j-1-a[i]]を減算するのである。

説明が長い上にわかりにくい文ですごめんなさい