【Python】動的計画法をやってみる

Python

動的計画法のアルゴリズムには前から興味があったが、なかなか身につかなかった。どのようなものか理解するために単純な問題を動的計画法で解いてみることにする。

動的計画法とは

動的計画法は、決まったアルゴリズムを指すものではなく、より広い概念である。動的計画法は、以下の2つの要素から構成される。 - 問題の分解: 問題を部分問題に分割し、その答えを使うことで全体の問題を帰納的に解く。 - 部分問題の結果の記録: 部分問題の答えを記録しておき、それを使うことで重複する処理をなくす。

部分問題への分解ができるような問題であれば、動的計画法が使える。今まで理解できていなかったのは、この定義を十分に押さえないまま、いろいろな問題の応用的な実装例ばかり見ていたせいだったのかもしれない。

動的計画法を使って問題を解く

AtCoderのABC049Cを解いてみる。この問題は過去問精選で紹介されていたが、まだ解いていなかった。

atcoder.jp

英小文字からなる文字列 Sが与えられます。 
T が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S = T とすることができるか判定してください。
・T の末尾に dream dreamer erase eraser のいずれかを追加する。

後ろから順に見ていくという簡単な解法もあるが、動的計画法の場合、Sのうち任意のn文字目までについて、問題で指定されている単語で作ることができるかを記録していく。n文字目までを作れるかと、その状態からn+1文字目以降を作っていくことができるかとは完全に独立した話なので、部分問題として分割して結果を記録することで、その結果を再利用することができる。

S = input()
dp = [0] * (len(S) + 1)
dp[0] = 1

words = ["dream", "dreamer", "erase", "eraser"]
done = 'NO'

for i in range(len(S)):
    if dp[i] == 0:
        continue
    for w in words:
        if S[i:i+len(w)] == w:
            dp[i+len(w)] = 1
    
    if dp[len(S)] == 1:
        done = 'YES'
        break

print(done)

dp[i] は、文字列Sのi文字目までを words の単語で作れるかを表し、作れる場合は1を入れる。スタート時のために dp[0] = 1 としておいた。
それぞれのループでは、i+1文字目から見て、最初の部分文字列が words の中の単語になっているかを確認する。例えば dream が作れれば、 dp[i+5] を1とする。こうすることで、 dp[i] が1でなければスキップして次のループに行くという処理ができる。
この処理ではループを2回使っているが、 words が定数種類しかないため、計算量は O(n) とみなせるだろう。

動的計画法の使い所

今回はごく単純な例だったが、動的計画法はより複雑な組み合わせ問題のときに力を発揮する。例えばナップザック問題のように、複数のパラメータを自由に変えて最適な組み合わせを求めるような問題の場合、 部分的な最適解をメモしておけば、効率的に解くことができる。パラメータを1つずつ変化させていったとき、同じパラメータの値の組み合わせが異なる場所で登場するような問題であれば、なおさら再利用の効果が高い。