ツバサの備忘録

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

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

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

問題

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]通りの組み合わせが考えられます。
そして、k0から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,1_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の範囲について調べてみると、jj-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)まで計算量を落とすことができました。