動的計画法

日曜の東大での模擬練習会はしょぼーんな結果に終わったり Firefox 2.0 がリリースされたりしたけど、今日は動的計画法の数度めの勉強をした。先輩には何度も同じ説明をさせて申し訳ない…。

探索系の、いわゆるトップダウンに書いてく手法に慣れてたのと DP に苦手意識? 持ってることもあり、なかなか理解が進まない。受けた説明は既に 3 回目くらいかも。まあ、さっさと手を動かして体得しろという話もある。

というわけで、 147 Dollars を解いた。

数種類のコインを使ってある金額を払う。与えられた金額に対して支払い方（コインの組み合わせ方）は何通りか、という問題。コインも与えられる金額も全て 5 の倍数なので 5 で割っとくと領域的にもお徳らしい。

最初は深さ優先探索で書いて、あっさり Time Limit Exceeded を受領。これは DP ですか。

コインの種類は固定なため組合せは変わらないので、最初に全て生成。つまり、あるコインを使って支払うとこの金額は何通り、というのを表にずらずら並べていきます。

上の図では行がコインの種類、列が金額。とりあえず一行目を 1 で初期化。考え方としては、例えば金額 10 を価値 5 のコインで払うやり方は 1 通り、という感じ。価値 0 は払い方が 0 パターンでこれも一つの組合せと考える、としてもいい。

そんで次の行へ。この行では価値 5, 10 のコインを使って支払い方の総数を考えます。例えば金額 10 の支払い方。これは:

1. 金額 10 の価値 5 のコインでの支払い方
2. 金額 0（= 金額 10 – 価値 10） の価値 5, 10 のコインでの支払い方

これらの和と考えられる。

ここらへんの理解が危うい感じです。「考えられる」とか書きながらもほんとかよ! と突っ込みたくなる。うまく説明できない。

更に次の行。金額 30 を価値 5, 10, 20 のコインで支払う組合せは:

1. 金額 30 を価値 5, 10 のコインで支払う組合せ数
2. 金額 10（= 金額 30 – 価値 20）を価値 5, 10, 20 のコインで支払う組合せ数

の和です。図の矢印を辿ってみればなんとなく分かるかと。

これを繰りかえしていくと、表がどばーっと埋まっていきます。こんな感じで既に埋めたセルを元に新たなセルを埋めるという感じが DP なのだそうな。あと図では表なのでそのままコードにすると二次元配列取りますが、この程度の DP は一次元配列で書くのが普通だと。

とまあ、うまく説明も出来ずに久々のエントリは終わるのであった。（何