🐕

動的計画法（動的プログラミング）

2023/02/22に公開

Python

動的計画法（Dynamic Programming:DP）は特定クラスの問題を解決するためのとても強力な技術です。与えられた入力で問題を解いた場合、同じ問題を再び解かないように、将来の参照のために結果を保存します。与えられた問題をより小さな問題に分割し、その小さな問題をさらに小さな問題に分割し・・・その過程で、いくつかの重複する問題を見つけたら、それはDPの大きなヒントとなります。分割した小さな問題の最適解は、与えられた問題の最適解に寄与します（部分構造最適性（Optimal Substructure Property）という）。

これには2つの方法があります。

トップダウン
与えられた問題を分解して解き始めます。もし、その問題がすでに解かれていたら、保存されている答えを返します。解かれていない場合は、解いて答えを保存します。これを「記憶（Memorization）」と言います。
ボトムアップ
問題を分析し、小問題の解答順序を確認し、些細な小問題から、与えられた問題に向かって解き始めます。このプロセスでは、問題を解く前に部分問題を解くことが保証されています。これを動的計画法と言います。

再帰法と動的計画法

再帰法は、問題を解くためにトップダウンを用いており、メインの問題を小問題に分割し、小問題も同様に解決します。この方法では、同じ小問題が複数発生し、CPU をより消費する可能性があります。したがって、時間計算量が増加します。

一方、動的計画法では、同じ小問題は複数回解かず、前回の結果を用いて最適化します。

フィボナッチ数列を例に考えてみましょう。

# （定義）フィボナッチ数列
Fib(n) = Fib(n-1) + Fib(n-2)

# n = 4 とすると
Fib(4) = Fib(3) + Fib(2)
= (Fib(2) + Fib(1)) + Fib(2)
= ((Fib(1) + Fib(0)) + Fib(1)) + Fib(2)
= ((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0))

ここで、Fib(1) と Fib(0) が複数回呼び出されています。n = 100 だとすると、これらが呼び出される回数はとても多くなります。したがって、CPU やメモリなどのリソースの無駄ができます。

フィボナッチ DP 法

トップダウン・フィボナッチ DP 法は、各フィボナッチ数の計算結果をテーブルに保存しておき、同じ値の再計算をなくす方法です。

非 DP 法と DP 法で求めるフィボナッチ数を Python で実装した例を示します。

fibonacci.py

# （定義）フィボナッチ数列
# Fib(n) = Fib(n-1) + Fib(n-2)

memo = [0] * 10 # 計算結果を保存するリスト
# memo = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# 非 DP 法（再帰法）
def not_dp(n):
  if n == 1 or n == 2:
    return 1
  else
    return non_dp(n - 1) + non_dp(n - 2)

# トップダウン DP 法（記憶：Memorization）
def top_down_dp(n):
  if n == 1 or n == 2:
    return 1
  if memo[n] != 0:
    return memo[n]
  memo[n] = top_down_dp(n-1) + top_down_dp(n - 2)
  return memo[n]

# ボトムアップ DP 法（直前の計算結果のみ保存する）
def bottom_up_dp(n):
  memo1 = 1
  memo2 = 1
  for i in range(3, n + 1):
    memo = memo1 + memo2
    memo2 = memo1
    memo1 = memo
  return memo

ボトムアップ DP 法 > トップダウン DP 法　の順番で早くなります。

動的計画法（動的プログラミング）

再帰法と動的計画法

フィボナッチ DP 法

参考文献

Discussion