Dynamic Programming (DP for short) という概念について（WIP）

Computer Scienceの世界ではお馴染みのMaximum Path Sum系の問題なんかでよく使われたりする概念。あとはCSのための数学みたいな授業を取ったことある人も触れたことあるかもしれない。今日はざっくりと簡単に説明。

Dynamic Programmingとは

結論から言うとRecursion + memorization + guess (as in trying all possibilities)

1. 問題を小問題に分ける

1. その小問題って見たことある？yes -> 3 No -> 4
2. 見たことあるのでノートを参照して答えをだす
3. 見たことないので計算処理をして答えを出す。その答えをノートに書き写す。
4. 1-4の繰り返し。

処理に必要な時間は小問題の数（=n）*時間/小問題（=O(1)）。recursionは計算に入れる必要はない。

shortest pathとかに最適なアルゴリズム。検索系にも。

Fibonacci

fib.py

def fib(n):
    if n <= 2: f = 1
    else: f = fib(n-2) + fib(n-1)
    return f

フィボナッチ数列として有名な関数であるがこの書き方は効率が悪い。処理中に同じ計算が何度も行われているからだ。F(2)なんて3回も行われている。関数の中に保存されているデータは（引数として入れていない限りは）一時的なものである。言い換えれば関数はその役割を果たしてしまうとその処理に関するデータをすっかり忘れてしまうイメージ。こうした点においてrecursive algorithmはあまり効率的ではないと言える。(->T(n) = T(n-1) + T(n-2) + O(1) = O(2**n/2)

F(5)  
                    /      \                  
                   /        \
                  /          \
               F(4)          F(3)
            /       \        /   \
          F(3)     F(2)     F(2)  F(1)
         /   \     /  \     /   \
       F(2) F(1) F(1) F(0) F(1) F(0)
       /  \
     F(1) F(0)

そこで一度処理したデータ（例えばF(2)）を保存して必要な時にアクセスできるようにしたらどうか。ここで出てくるのがDynamic Programmingである。

dp_fib.py

storage = {}
def fib(n):
    if n in storage: return storage[n]
    if n <= 2: f = 1
    else: f = fib(n-1) + fib(n-2)
    storage[n] = f
    return f

簡略的ではあるがイメージとしてはこんな感じだろうか。

F(5)  
                    /      \                  
                   /        \
                  /          \
               F(4)          F(3)
            /       \        /   \
          F(3)     F(2)     F(2)  F(1)
                           /   \
                          F(1) F(0)

もっと効率的な方法を探しているのであれば

fib.py

n = input("some number: ")
fib = {}
for k in range(1, n+1):
    if k <= 2: f = 1
    else: f = fib[k-1] + fib[k-2]
    fib[k] = f
print(fib[n])

参考

• Demystifying Dynamic Programming