動的計画法（その 1）

「動的計画法」は、より小さい問題の結果を利用して本命の問題を解くアルゴリズム設計技法です。英語では Dynamic Programming と書くため、略して DP と呼ばれることもあります。

以前に紹介した二分探索法や貪欲法などと比べ、DP はさらに応用範囲が広いアルゴリズムです。そこで、今回も 2 回に分けてさまざまな例題を取り上げていきます。まずは、貪欲法の解説（第6回記事） でも登場した「紙幣の問題」です。

第6回「“1手先だけ”を考える『貪欲法』」はこちらから

例題 1：紙幣の問題～貪欲法で解けない場合～

4 千円札^※1・3 千円札・1 千円札を使って最小枚数でピッタリ 6 千円を支払う方法を考えてみましょう。直観的には「大きい金額の紙幣から順番に取っていく」という貪欲法的な戦略をとることで、解決できそうに思えます。しかしながら、実際は下記のようになり、最小枚数を求めることができていません。

• 貪欲法： 3 枚（4 千円 + 1 千円 + 1 千円）
• 最適解： 2 枚（3 千円 + 3 千円）

では、一体どうすれば良いのでしょうか^※2。

そこで以下のように、小さい問題から順に 1 つずつ計算していくことを考えましょう。

• 0 円を支払うために必要な最小枚数 dp[0] を求める（明らかに 0）
• 1 千円を支払うために必要な最小枚数 dp[1] を求める
• 2 千円を支払うために必要な最小枚数 dp[2] を求める
• 3 千円を支払うために必要な最小枚数 dp[3] を求める
• 4 千円を支払うために必要な最小枚数 dp[4] を求める
• 5 千円を支払うために必要な最小枚数 dp[5] を求める
• 6 千円を支払うために必要な最小枚数 dp[6] を求める

下図のような計算過程により、最小 2 枚で 6 千円を支払えることが分かります。このように、より小さい問題の結果を利用して答えを求めるアルゴリズムは動的計画法（DP）と呼ばれています。

なお、dp[1], dp[2], ……, dp[6] の値は、最後の行動で場合分けをすると計算しやすいです。例えば、 6 千円を支払うために必要な最小枚数 dp[6] は、以下のようになります。

• 5 千円払った状態から、最後に 1 千円札を使って支払うとき： 必要枚数は dp[5] + 1 = 3 枚
• 3 千円払った状態から、最後に 3 千円札を使って支払うとき： 必要枚数は dp[3] + 1 = 2 枚
• 2 千円払った状態から、最後に 4 千円札を使って支払うとき： 必要枚数は dp[2] + 1 = 3 枚

このことから、答えはこれらの中で最も少ない 2 枚であると分かります。

※1　3 千円札、4 千円札は実在しませんが、便宜上、これらの紙幣を使って考えていきます。

※2　もちろん、使用する 4 千円札・3 千円札・1 千円札の枚数を全探索しても簡単に答えが分かりますが、支払う金額（ここでは 6 千円）が大きい場合は計算に時間がかかるため、あまり実用的ではありません。