動的計画法における重複組み合わせの式変形について

蟻本に載っている重複組み合わせの式変形がピンとこなかったので、頭の整理をするためにメモを。

問題

$n$ 種類の品物が存在し、 $i$ 番目の品物が $a_i$ 個あるとき、これらの中から $m$ 個選ぶ組み合わせの総数を求めよ、というものになります。

解法

まずは $O(nm^{2})$ の解法からです。
$dp[i][j]=i$ 番目までの品物の中から $j$ 個選ぶ組み合わせ
のようにすると、
$i$ 番目の品物を $k$ 個選んだときに選んだ品物が合計 $j$ になるようにするには、 $i-1$ 番目までの品物で $j-k$ 個選んでいればよいので、 $dp[i-1][j-k]$ 通りの組み合わせが考えられます。
そして、 $k$ は $0$ から $min(j,a_i)$ までが考えられるので、最終的な遷移は
$dp[i][j]=\Sigma_{k=0}^{min(j,a_i)}dp[i-1][j-k]$
となります。
これを、うまく式変形することで、計算量を落とします。この式変形を何も見ずに行った人はかなりの猛者ではないかなと思います…
方針としては、今式に表れているシグマの部分を、どこかほかの配列を参照できるようにすることで、kのループを削除する、というものになります。
前提として、配列の添え字が負になっているときは、その中身は0であるとします。

まず、先ほどの式のうち、 $j-k$ の部分を、 $j-k-1$ にずらします。
$k$ の範囲はそのままにするので、 $1$ ずらすことで、余分なものと足りないものが一つずつ現れます。なので、その部分を調整します。
足りなくなったものは、ずらす前には存在した、 $k=0$ のときの $dp[i-1][j]$ になります。これをシグマの外で足してあげます。
逆に余分になったものは、ずらした後の最後の部分、 $dp[i-1][j-min(j,a_i)-1]$ になります。これをシグマの外で引いてあげます。
もうすこし整理すると、 $dp[i-1][j-min(j,a_i)-1]$ は、

$min(j,a_i)$ が $j$ のとき
$dp[i-1][-1]$
となり、 $0$ になります。
このとき、 $j-a_i-1$ も負であるので、
$dp[i-1][j-a_i-1]$
も $0$ です。
$min(j,a_i)$ が $a_i$ のとき
$dp[i-1][j-a_i-1]$
となります。

よって、どちらの場合でも $dp[i-1][j-a_i-1]$ でカバーできていることになります。これで少しだけ式をスッキリさせることができました。
ここまでの操作を整理して式変形をまとめると、
$dp[i][j]=\Sigma_{k=0}^{min(j,a_i)}dp[i-1][j-k-1]+(dp[i-1][j]-dp[i-1][j-a_i-1])$
となります。ところで、 $k$ の範囲について調べてみると、 $j$ は $j-1$ でいいことがわかります。
なぜなら、

$min(j,a_i)$ が $j$ のとき
$dp[i-1][j-j-1]$ は $dp[i-1][-1]$ なので $0$ となります。
$min(j,a_i)$ が $a_i$ のとき
$j > a_i$ なので、 $k=j$ となることはありません。

ということで、さらに式変形をすると、
$dp[i][j]=\Sigma_{k=0}^{min(j-1,a_i)}dp[i-1][j-k-1]+(dp[i-1][j]-dp[i-1][j-a_i-1])$ となります。
最後に、
最初の項は $dp[i][j-1]$ そのものなので置き換えることができ、
$dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-a_i-1]$
となります。
これで、 $O(nm)$ まで計算量を落とすことができました。

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

動的計画法における重複組み合わせの式変形について

問題

解法