動的計画法とは何か？アルゴリズムをわかりやすく解説！

みなさんは動的計画法というアルゴリズム設計技法をご存じでしょうか。
情報系の学部の人が専門の講義や研究で必ず一度は通るアルゴリズム、それが「動的計画法(Dynamic Programming)」です。

動的計画法は、他のアルゴリズム(例えばソートアルゴリズムや二分探索)と違って癖が強く、つまづく人も多いです。
実際私の知り合い(情報系学部2年生)も、
「アルゴリズムの授業では今まで苦戦したことなかったのに、動的計画法に入ってから一気に意味不明になった。」
と苦しんでいる様子でした。

今回の記事では、

動的計画法のイメージをつかみたい
動的計画法を使った問題を解きたい

という人向けに、動的計画法について具体的な問題例を使いつつ解説しました。
ぜひ最後まで読んで、動的計画法のイメージをつかんでもらえればと思います。

動的計画法の簡単な解説

動的計画法は、アルゴリズムそのものというよりは、「アルゴリズムを設計するためのアプローチの1つ」と思ってもらえるといいと思います。
つまり、動的計画法の考え方を利用して、様々な派生アルゴリズムを設計することができるという訳です。

それで結局、動的計画法はどういうものかというと、以下のような手順でアルゴリズムを設計することをいいます。

Aという大きな問題を解きたいとします。
まず、AをBという中くらいの問題に分解します。
つぎに、BをCという小さい問題に分解します。
出てきたCを順番に解きます。この時求めた解をテーブルに記録しておきます。
テーブルの解を使ってBを順番に解きます。Bの解をテーブルに上書きします。
テーブルの解を使ってAを解きます。

このようにして動的計画法では、元の問題を分解していき、十分小さくなったら問題の解を求め、あらかじめ領域を確保しておいたテーブルに記録します。
そしてそのテーブルの記録に基づいて、だんだん大きい問題が解けていく仕組みなのです。

つまり、動的計画法は以下の性質を持ちます。

問題をスケールの小さい別の問題群に分解する
結果はテーブルにメモしていき、それを利用して次のステップを行う

動的計画法の計算量

計算量とは何か？

ここで、アルゴリズム設計で最も重要な指標である「計算量」について簡単に解説しましょう。

計算量というのは、アルゴリズムを使ってある問題を解くのにかかる計算の回数のことです。

例えば10000回の計算を、2重forループで回すようなアルゴリズムを作ったとします。
すると結局、\(10000 × 10000 = {10}^{8}\) 回の計算を行うことになります。
これを計算量で記述する時には、\(O({10}^{8})\)と書きます。

また、\(2 × {10}^{8}\) 回の計算を行った場合でも、計算量として書く場合は\(O({10}^{8})\)になります。
あくまで、最も影響の大きい部分だけを記述することに注意してください。

動的計画法の計算量はどうなるか？

では、結局動的計画法を使ってアルゴリズムを設計した場合の計算量はどうなるのでしょうか。

これは問題によっても異なるのですが、動的計画法が有効な場合、計算量は以下のようなイメージです。

「愚直解を使って問題と解こうとした場合の計算量の\(\log\)を取ったものの何倍か」

あくまで大体なので、定理として存在するわけではありません。

例えば「動的計画法を使って解く問題Ⅰ : 0-1ナップサック問題」での計算量ですが、目安通りの計算を行った場合、
\(元々の計算量 : O(2^{n})　→ \log を取るとO(n)　→　定数倍してO(nm)\)
となり、これは実際の「動的計画法を使って0-1ナップサック問題を解いた場合の計算量」と一致しています。

動的計画法のパワーを知る問題 : フィボナッチ数列

それではいよいよ、実際に動的計画法を使った例を見ていくことにします。

1つめは「フィボナッチ数列」というテーマです。
これはかなり有名な数列で、動的計画法を使ってアルゴリズムを設計することでスムーズに高次の項を求めることができます。

フィボナッチ数列とは何か？

フィボナッチ数列を知らない人のために、「フィボナッチ数列とは何か」を解説しておくことにします。
概要は以下の通りです。

初項は1、第2項は1で、第3項以降は前の2項を足した値になるような数列

となります。
具体的な数式で書くと、自然数\(n\)に対して、

\(f(1) = 1\)
\(f(2) = 1\)
\(f(n+2) = f(n+1) + f(n)\)

という風に漸化的に求めることのできる数列ということです。

フィボナッチ数列を題材とした実際の問題例

AIZU ONLINE JUDGEという、アルゴリズムを学習するサイトにフィボナッチ数列を実際に実装する問題があります。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja

問題をまとめて再掲すると、「44以下の自然数nに対して、フィボナッチ数列の項を求めよ」になります。
このセクションではその問題に対する動的計画法の適用を考えます。

1. 単純に再帰的に解こうとした場合

まずは、特に何も考えず愚直に問題を解こうとした場合を考えます。
方針としては以下の通りです。

[愚直解の方針]
\(f(x)\)を\(x\)が\(1\)または\(2\)になるまで分解しつづける。
つまり、

\(x = 1\) or\(2\) なら\(1\)を返す
それ以外なら\(f(x-1) + f(x-2)\)を返す

Pythonでこの解法を実装すると以下のようになります。

def fib(x):
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

n = int(input())
print(fib(n))

この場合の計算量は指数関数になってしまいます。
なぜなら、何回も同じ無駄な計算をしているからです。

例えば\(f(3)\)は高次の項を求めるときに何回も出てきますが、そのたびに同じ計算をしています。
それも1回や2回ではなく、何十回を同じ計算を繰り返すはめになります。

詳しい説明は省略しますが、結局のところ\(O({(\frac{1+\sqrt{5}}{2})}^{n})\)の計算量になることが知られています。

2. 動的計画法を使って解いた場合

このように、愚直解の計算量は指数関数になってしまい、ちょっと\(n\)が大きくなると対応できなくなるプログラムになってしまいました。
非常に無駄が多く、実用的でないコードを言わざるを得ません。

今度は、動的計画法をつかってフィボナッチ数列の高次項を求めることを考えてみましょう。

具体的には、動的計画法の入り口である「メモ化再帰」というのを使います。
メモ化再帰のやり方は以下の通りです。

初めて計算する(テーブルに結果が記されていない)場合には、計算を行って結果をテーブルに記録する。
テーブルに結果が記されている場合は、その結果をそのまま使う。

メモ化再帰を用いて、フィボナッチ数列の問題をpythonで実装すると以下のようになります。

max_n = 55
n = int(input())
table = [0] * max_n

def fib(x):
    if x==1 or x==2:
        return 1
    else:
        if table[x]==0: #記録されていない場合のみ計算を行って記録する
            table[x] = table[x-1] + table[x-2]
        return table[x]

print(fib(n))

この場合、各自然数に対して1度のみ計算が行われることが分かります。
つまり、計算量としては\(O(n)\)で済んでしまうというわけです。
先ほどの無駄な計算の手間が全て省略され、あっという間に高次の項を求めることができるようになりました。

一次関数と指数関数、動的計画法の計算量と愚直解の計算量とでは、天と地の違いがありますよね。
これが動的計画法のパワーと言っていいでしょう。

動的計画法を使って解く問題 : 0-1ナップサック問題

0-1ナップサック問題とは何か？

0-1ナップサック問題の実際の問題文は以下の通りです。

\(n\)個の品物があり、\(i\)番目の品物の重さ\(w_i\)と価値\(v_i\)と定義されている \((i=0,1,...,n−1)\)。
これらの品物から重さの総和が\(W\)を超えないように選んだときの、価値の総和の最大値を求めよ。

[制約] \(1 \leq n \leq 100\)
\(1 \leq w_i, v_i \leq 1000\)
\(1 \leq W \leq 1000\)

シンプルに「\(n\)個の荷物それぞれを使う or 使わない場合を調べる」という全パターンを試すやり方だと、計算量が\(O(2^{n})\)になってしまい、制約の条件から計算することができません。
動的計画法を使うことで少ない計算量で解くことができます。

0-1ナップサック問題の解答方針

この問題も、先ほどのフィボナッチ数列のように「メモ化再帰」を基本とした動的計画法を行うことで解くことができます。

ただし先ほどは1次元のテーブルだったのに対し、ナップサック問題では2次元のテーブルを用意する必要があります。
つまりmemo[maxvalue * n][maxweight * n]という大きさの配列をあらかじめ準備しておきます。

そして、memo[i+1][j]を以下のように定義します。

i番目までの品物の中から、重さがjをこえないように選んだときの価値の総和の最大値

さて、これを使って動的計画法を実装します。
つまり、memo[i][j]の値を利用して、memo[i+1][j]を求めることを考えるのです。
memo[i][j]に、i番目の荷物の情報を加味してよりよい解を見つけ、memo[i+1][j]に代入する、というわけです。

まず以下の2つに場合分けをします。

weight[i]\(\leq\)jの場合 (i番目の荷物がナップサックに入る場合)
weight[i]\(>\)jの場合 (i番目の荷物がナップサックに入らない場合)

前者の場合は、i番目の荷物をナップサックに入れる or 入れないの選択肢を取ることができます。
一方で後者では、i番目の荷物はスルーするしかないというわけです。

具体的には、それぞれの場合でmemo[i+1][j]は以下の値を取ります。

weight[i]\(\leq\)jの場合
- 1.1 荷物を入れる : memo[i+1][j] = memo[i][j-weight[i]] + value[i]
- 1.2 荷物を入れない : memo[i+1][j] = memo[i][j]
weight[i]\(>\)jの場合
- 2.1 荷物を入れない : memo[i+1][j] = memo[i][j]

1.1の補足をしておくと、i番目の荷物を入れるので残った重さのキャパシティは j-weight[i] になりますよね。
なので、memo[i][j-weight[i]]で、「i-1番目までの範囲で、j-weight[i]の重さの範囲で一番高い価値」を求めて、それとvalue[i]を足すことで、荷物を入れる場合のmemo[i+1][j]が求まるというシステムになります。

というわけで、memo[i][j] から memo[i+1][j] を求めるには以下のような記述をすればよいことになります。

if weight[i] <= j:
    memo[i+1][j] = max(memo[i][j-weight[i]] + value[i] , memo[i][j])
else:
    memo[i+1][j] = memo[i][j]

これをiの小さいほう、jの小さいほうからforループで回していけば、全てのi,jに対してmemo[i][j]を求めることができます。

計算量は、全てのi,jに対して計算を一度のみ行うので、\(O(nW)\)で求めることができます。

Pythonによる0-1ナップサック問題のソリューション

以上の点をふまえて、0-1ナップサック問題を解くソースコードを実装した結果が以下になります。

max_n = 105
max_w = 10005
memo = [0 * max_n] * max_w
weight = [0] * max_n
value = [0] * max_n

n = int(input())
W = int(input())

# 入力
for i in range(n):
    weight[i] = int(input())

for i in range(n):
    value[i] = int(input())

# 初期値の設定(重さがゼロなら価値も当然ゼロ)
for j in range (max_w):
    memo[0][j] = 0

# 動的計画法
for i in range (n):
    for j in range(W+1):
        if weight[i] <= j:
            memo[i+1][j] = max(memo[i][j-weight[i]] + value[i], memo[i][j])
        else:
            memo[i+1][j] = memo[i][j]

print(memo[n][W])

おわりに

今回は動的計画法の解説・使用例を見てきました。
取り扱ったフィボナッチ数列・0-1ナップサック問題以外にも、動的計画法は様々な場面で応用することが可能です。

部分和問題
(個数制限なしの)ナップサック問題
敷き詰め問題
画像圧縮

などの問題を解くアルゴリズムに使われていますので、興味のある方はぜひ調べてみてください。