DP強化月間 - れどこだ目指すよ！　(；`・ω・）

動的計画法(DP)は強力な武器なので、ぜひマスターしたい、でも、うまく適用できない。。
そんな感じなので、今月はできる限りDPの問題を解いて、DP力を上げるようにがんばります。

ということで、topcoderのalgorithm tutorialsのDPのところを読みながらやっていきたいと思います。以下は自分的訳なので、わかりずらい可能性大。
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Dynamic Programming : From novice to advanced (by Dumitru)の自分訳

問題を解くうえで、動的計画法(略してDP)は大きな助けになります。
DPの問題が解けるようになれば、あなたのスキルは大きく向上するでしょう。
ここでは、DPを使って問題を解く方法を説明します。
この記事では、動的計画法の元の理論をちゃんと理解するのは難しいので、例題をベースにやります。
注意:わかっているセクションは飛ばしてどんどん次をやってください。

入門

■動的計画法って何？
DPとは、ひとつ(もしくはいくつか)の初期状態と再帰的な式に基づくアルゴリズムテクニックです。問題の部分解(Sub-Solution)は、前に見つけた部分解からどんどん見つけていきます。DP解法は、バックトラック法や全探索(brute-force)などのアルゴリズムよりも実行時間が非常に速いことが保障されます(多項式複雑性)。
まず、DPの基礎を例題で見てみましょう。

N枚のコインの種類のリスト(V1,V2,...,VN)と合計Sが与えられます。
合計がSであるようなコインの最小数を見つけなさい
(各コインは十分なコインが用意されているとする)。
もしくは、そのようなコインの選択がないかどうかを示しなさい。

では、DP解法を作り始めましょう。
まず、最適解が見つかるような、そして次のstateで最適解を見つけられる助けとなるようなstateを見つける必要があります。

■stateって何？(何を表すのか？)
state(以下、状態)は、ある状況(問題の部分解)を表現する手段です。上の例では、コインの合計がiであるような解(i<=S)が状態として考えられます。j

基本的にDPは、表を書いたりして、漸化式が立てるかどうかによると思う。
結局iを求めるために、j

■どうやってそれを見つけるの？
んなのは簡単です。
各コインj(Vj<=i)について、すでに見つけているはずの合計がi-Vjでの最小枚数に注目します。この最小枚数をmとすれば、i-VjにVjのコイン1枚を足したm+1枚が、すでに計算してある(合計iの)最小枚数よりも少なければ、より最適な結果としてm+1を採用します。

例として、{1,3,5}のコインで合計S=11だった場合を考えます。
状態0(合計が0)というのは、別にコインは必要じゃないので最小枚数が0だということはわかります。次に合計が1を考えると、1-V1=0はすでに状態0が分かっているので枚数1枚でできます。V2,V3では(マイナスになってしまうので)合計1を作れません。したがって、状態1での最小枚数は1枚になります。
2枚の時は、状態0と状態1の最小枚数が分かっているので、それを使って計算し、それぞれV1なら2枚(2-V1=1なので、状態1を見ると最小枚数は1枚なので、1+1=2枚)、V2,V3はi-V2,i-V3がマイナスになるので作れず、最小枚数が1枚だとわかります。
これを状態11まで繰り返すことで、最小枚数を見つけることができます。
疑似コード:

Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1

Output Min[S]

見つけたすべての解を表にすると、

合計	コインの最小枚数	加えたコインの種類(と加えた元の合計)
0	0	-
1	1	1(0)
2	2	1(1)
3	1	3(0)
4	2	1(3)
5	1	5(0)
6	2	3(3)
7	3	1(6)
8	2	3(5)
9	3	1(8)
10	2	5(5)
11	3	1(10)

加えて説明すると、上の表の一番右の情報(どの金額にどのコインを加えたか？)も保持しておくと、その合計を作るための方法をさかのぼって突き止めることができます。
例えば、合計11をつくるために合計10にコイン1を加えました。合計10を作るために合計5にコイン5を加えました。合計5を作るために合計0にコイン5を加えました。
したがって、コイン1が1枚とコイン5が2枚という最小枚数3枚で合計11を作れることがわかります。

ちょっと違った方法として、Vjの引き算ではなく足し算でもできます。
上の方法では、状態iでi-Vjを考えることで最小枚数を計算しました。
逆に、状態iが最適な枚数であるならば、i+Vjを考えれば、状態iでm枚ならば状態i+Vjはm+1枚でできます。なので、その最小枚数を保持するようにすれば、状態i+Vjを計算するときにその枚数は最適になっているはずです。

初級

まだ

中級

まだ

中上級

まだ

上級

まだ

Dynamic Programming : From novice to advanced (by Dumitru)の自分訳

入門

初級

中級

中上級

上級

関連の問題