「動的計画法」は、より小さい問題の結果を利用して本命の問題を解くアルゴリズム設計技法です。英語では 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 千円）が大きい場合は計算に時間がかかるため、あまり実用的ではありません。

例題 2：階段の上り方

次に紹介するのは、階段を上る方法が何通りあるかを求める問題です。

太郎君は N 段の階段を上ろうとしています。彼は一歩で 1 段か 2 段上ることができます。0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを計算してください。

制約： 1 ≤ N ≤ 45

実行時間制限： 1 秒

出典： アルゴリズムと数学 演習問題集 029 - Climb Stairs

まずは具体例として N=5 の場合を解説します。いきなり答えを求めるのは難しいので、以下のような順番で計算していくことを考えましょう。

  • 0 段目から 0 段目まで上る方法の数 dp[0] を求める（明らかに 1 通り）
  • 0 段目から 1 段目まで上る方法の数 dp[1] を求める（明らかに 1 通り）
  • 0 段目から 2 段目まで上る方法の数 dp[2] を求める
  • 0 段目から 3 段目まで上る方法の数 dp[3] を求める
  • 0 段目から 4 段目まで上る方法の数 dp[4] を求める
  • 0 段目から 5 段目まで上る方法の数 dp[5] を求める

さて、dp[2], dp[3], dp[4], dp[5] を求めるにはどうすれば良いのでしょうか。例題 1 と同様、最後の行動で次のように場合分けをすると、dp[n] = dp[n-1] + dp[n-2] という漸化式を導くことができます。

n (≥ 2) 段目に上る方法として、以下の 2 つがあります。

  • パターン A： 0 段目から n-1 段目まで上った後、一歩で 1 段上る
  • パターン B： 0 段目から n-2 段目まで上った後、一歩で 2 段上る

そこで、パターン A・B で上る方法の数はそれぞれ dp[n-1] 通り、dp[n-2] 通りです。このことから、n 段目まで上る方法の数が dp[n-1] + dp[n-2] 通りであると言えます。

この式に従って n = 2, 3, 4, 5 の順に計算すると下図のようになり、答えは 8 通りだと分かります。

N=5 以外のケースでも、漸化式に従って n = 2, 3, ……, N の順に計算すると答えが得られます。以下のプログラムは Python での実装例であり、計算量は O(N) です。

# 入力 / 配列の初期化
N = int(input())
dp = [0 for i in range(N + 1)]

# 答えを求める
dp[0] = 1
dp[1] = 1
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

# 出力
print(dp[N])

＊　＊　＊

このように、「より小規模な問題」の結果を利用する DP を使うと、問題を効率的に解ける場合があります。

今回は「紙幣の問題」「階段の上り方」の 2 つを紹介しましたが、DP はさらに広い範囲で使えます。次回は応用編として、「ナップザック問題」を紹介します。楽しみにお待ちください。