背景
筆者のレベル
AtCoderはこれまでに１０回参加しました。現在は灰色です。過去問ではCはほぼ解き終えて、現在D問題に着手しています。茶色になりたい！
なぜこの記事を書こうとしたのか
AtCoderで茶色以上を目指すのであれば動的計画法（以降DP）は避けて通れません。脱初級者向けに学ばなければならいないアルゴリズムとしては例えば全探索（基礎から応用まで）、ビット探索、BFS、DFSなどあります。しかしDPは自分の見立てではこれらのアルゴリズムと比べると一段階～二段階難しいレベルと感じます。
難しい理由を考えてみました。
- 探索やBFS/DFSは考えかたとして直感的にわかりやすいが、コーディングに落とし込むところで知識が必要なる。しかしDPはそもそも考え方がややこしい。
- 最も基本となるDPでもコーディングでは再帰を利用する必要がある。
- 実際の競プロでは再帰を利用するとTLEになるため、工夫を加えたメモ化再帰もしくは漸化式を利用する。
- DPで選択する変数を間違えるとTLEになってしまう。
DP全般の基本を理解する場合には、素晴らしい記事がいくつもあるのでそちらをまず参考にしてください（後述）。
DPの基本を学ぶと、TLEにならないために速度をあげるチューニングが必要になります。この際に出てくるのが漸化式による記述方法です。例えば蟻本ならP52～P53で再帰を利用したDP、そしてP54～P56で漸化式を利用したDPについて記述しています。蟻本には漸化式について以下ような記述があります。
"慣れてくれば直接漸化式を作れるようにもなっていきます"
しかしこの記述だけで漸化式による考え方を理解するのは至難の業です。蟻本を読み、理解し、慣れたら、漸化式かけた！という人はこの記事を読む必要はありません。
この記事が対象にしている人
この記事が目的とするのはDPは何となく理解して、再帰およびメモ化再帰までは何となくかけるが漸化式の意味が理解できないという人です。
この記事では以下を記載しています。
- 漸化式によるDPの考え方をEducational DP Contest / DP まとめコンテストにおけるA問題 Flog 1を利用して説明します。
- 漸化式は、配るDPおよび貰うDP、両方について説明しています。
この記事では以下については記載していません。
- DPの基本的な考え方
- 再帰もしくはメモ化再帰の考え方
- 漸化式を利用したコーディング
参考にするべき記事
DPの基本がわからない人はまず以下の記事を読んでください。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
基礎をまなぶには全部読む必要はないと思います。チャプター1～3（Flog - A）まででDPの基本は完全といってもよいくらいに身に付きます。
DPコンテストFrog - A
DP問題としてはかなり基本になります。
| 項目 | |
|---|---|
| 環境 | 1～N番目までの高さが異なる足場があります。 |
| 初期値 | カエルは1番目にいます。 |
| ゴール | N番目まで移動します。 |
| 条件 | カエルは次もしくは２つ先の足場にジャンプできます。 |
| 変数 | カエルは今ある足場の高さと次の足場の高さがコストとなります。 |
| 目標 | 上記コストの最小値 |
貰うDP
貰うDPでは、いま対象とする要素についてその要素の値はどこからの値で更新するかを考えます。例えば足場３の値を更新したい場合、足場３は足場１もしくは足場２から来ます。よって、足場１もしくは足場２の値を利用して足場３の値を更新することを考えます。
全体概要
条件の整理
足場は6です。各足場の高さは配列Aとなります。
N=6
A=30 10 60 10 60 50
DPテーブルの作成
DPテーブルを利用して最適な値を算出します。足場は6番までありますのでDPテーブルは一次元で長さ6になります。要素6が目的とする値です。これを最小化します。
初期化
この時にDPが対象とする値が決まるわけですから、どの値で初期化をするか考えることは重要です。今回の場合には変数の値が少ないためにコストを選べばよいとわかります。このコストは位置=1の時点では0です。
足場２
貰うDPでは、いま対象とする要素についてその要素の値はどこからの値で更新するかを考えます。
足場２について考えてみます。カエルは１つもしくは２つ先の足場までジャンプできます。足場のひとつ前は足場１，二つ前はありません。よって足場２は足場１からしか値を受け取りません。
足場1におけるコストは0です（初期化）。また足場１と足場２の差は|30-10|=20です。よって足場に２に来るための最小コストは0+20=20となります。
足場３
さてこのステップが肝です。ここを理解すれば、最後のステップまで繰り返しになります。
カエルは足場３にどこからジャンプできるでしょうか。カエルは足場１もしくは足場２からジャンプできます。その場合足場１と足場２のコストを比較して、小さいほうを採用すれば、足場３に到達するための最小コストが算出できることになります。
足場１から足場３へのコスト
足場１の高さ＝３０に対して足場３の高さ＝６０になります。よって足場１→足場３へのコストは|30-60|=30となります。しかし今回求めるのは足場3までの合計コストになります。足場１におけるコストは0です。よって合計コストは0+30=30となります。
足場２から足場３へのコスト
足場２の高さ＝１０，足場３の高さ＝６０ですから、足場２→足場３へのコストは|10-60|=50となります。しかし足場２に到達する時点でコストが20かかっています。よって足場3へ到達するための合計コストはこの時点で20+50=70となります。
コストの比較
足場1→3と足場2→3を比べると30と70ですから最小コストは30となります。つまり足場3に達するためには、足場1→3が良いということがわかります。
繰り返し
足場3から最後までは上記の繰り返しになります。足場6のコストが算出された時点で、これは足場0から足場6へ移動するための最小コストになっています。
結論
結論としては足場6まではコスト40で移動できることが分かりました。ポイントは足場3における比較です。ここさえ理解できれば貰うDPは理解できます！
配るDP
配るDPでは、いま対象とする要素がどこに対して値を更新できるかを考えます。例えば足場１ならば、足場２及び足場３を更新できます。
全体概要
初期化
初期化のステップは貰うDPと同じです。
足場１
配るDPは現在の要素がどこの要素を更新できるかを考えます。足場１からジャンプできるのは足場２及び３ですから、このステップでは足場２および３について値を更新します。
足場１から足場2へのコスト
足場１の高さ＝３０に対して足場2の高さ＝1０になります。よって足場１→足場2へのコストは|30-10|=20となります。しかし今回求めるのは足場3までの合計コストになります。足場１におけるコストは0です。よって合計コストは0+20=20となります。
足場１から足場３へのコスト
足場１の高さ＝３０に対して足場３の高さ＝６０になります。よって足場１→足場３へのコストは|30-60|=30となります。しかし今回求めるのは足場3までの合計コストになります。足場１におけるコストは0です。よって合計コストは0+30=30となります。
最小コストの算出
足場２については、足場１以外からは来れませんので、足場２への最小コストは決定できました。しかし足場３についてはまだわかりません。しかし足場１のステップはこれで完了します。
足場２
配るDPではこのステップが肝です。ここを理解すれば、最後のステップまで繰り返しになります。
この時点で足場2におけるコストは決定しています。
次に足場２から到達できる足場３および足場４について更新します。重要なことは足場３および４の更新は足場２までのコストが決定しているから算出できるということです。
足場３についてみてみると、足場１から来た時と足場２から来た時の両方についてコストが算出されています。これを比較すると足場３におけるコスト＝３０となります。
繰り返し
足場3から足場5までは繰り返しになります。境界条件になりますが、貰うDPでは足場6まで処理しますが、配るDPでは足場5までになります。これは足場6について配る先がないからです。
結論
結論としては足場6まではコスト40で移動できることが分かりました。貰うDPでも配るDPでも結果は同じになります。ポイントは足場2における比較です。ここさえ理解できれば貰うDPは理解できます！