コラム 動的計画法

例えば、探し物が家の中にあるはずなのに見つからないとしましょう。そのときに、まず家を部屋ごとに分けます。そして、その各部屋を、また細かく分けます。例えば部屋を50m 四方くらいに分けていくとします。すると、その50cm四方の中に探し物があるかどうかは簡単に分かると思います。それを繰り返していくと、その部屋に探し物があるかがわかるはずです。

というように、いきなり答えを出すのが難しい問題（家に探し物があるか？）を解くときに、その問題を小さな問題（50cm四方の中に探し物があるか？）に分け、その小さな問題をすべて解くことで最終的な問題の答えを出す方法を、分割統治法といいます。

この分割統治法は、数学の問題を解くのにも使えます。中学受験をしようとしている、または経験した人なら、次のような問題を解いたことがあると思います。

この問題は、交点それぞれに、その交点まで行く道順の数を書き込んでいくことで答えが出せます。（下の図）例えば、図の点Aでは、点Aの左から来るのは6通り、下から来るのが4通りなので、点Aに行く道順は 6+4=10通りです。これを繰り返すと、右上まで行く道順は225通りと出ます。

この場合は、「全部で何通りあるか」という問題を、「ある交点まで行く方法は、それぞれ何通りか」という問題に分割しています。また、このように小さな問題を解くときに、他の結果を再利用（左と下の道順の数を利用して次の道順の数を求める）するような分割統治法のことを動的計画法といいます。

では、動的計画法を使って、１つ問題を解いてみましょう。