［アルゴリズム］動的計画(Dynamic Programming,DP)

ダイナミックプランニング法とは?

簡単に言えば、大きな問題を小さな問題に分けて解決する問題です.

ダイナミックプランニングフィーチャー

大きな問題を小さな問題ユニットに分割する場合は、重複を避けるために小さな問題を一度だけ解決します.次の特徴を持つために、ある場所で小さな問題の答えを見つけ、ある場所でより大きな問題を見つけた場合、同じ小さな問題に遭遇した場合は、以前に保存した小さな問題の結果値を使用します.

📝注記構造

前述したように、ダイナミックプランニング手法は、同じ小さな問題を繰り返す場合に、小さな問題の計算結果を格納し、これらの結果を用いて重複計算を低減する.これはMemoizationと言います.

再帰関数と動的計画法

再帰関数形式のフィボナッチ数列

def fibo(x):
    if x <= 2:
        return 1
    return fibo(x-1) + fibo(x-2)

fibo(6)の運転手順

実行中に、fibo(4)の操作が2回、fibo(3)の操作が3回行われるなど、繰り返しの操作が表示されます.
数字が小さいほど、この演算は良いが、数字がもう少し大きいと、時間の複雑さと空間の複雑さが指数関数的に増加する.

動的計画法

ダイナミックプランニング法は、以前に計算した値を保存して繰り返し計算を防止し、1回の演算が必要な場合は、1回の演算ではなく保存した値を取得します.
ダイナミックプランニング法で解くフィボナッチ数列

 def fibo(x):
    if x <= 2:
        return 1
    if mem[x] != 0:
        return d[x]
    mem[x] = fibo(x-1) + fibo(x-2)
    return d[x] 

xが2より小さい場合は1を返し、1より大きい場合はmem[x]に格納されている演算値がないかどうかを確認します.ない場合は、演算により値を保存しmem[x]に戻ります.保存した演算値が存在する場合、mem[x]がすぐに返されます.
TOP-DOWN
上から下へ、コメントを使用して作成
すなわち,大きな問題からずっと小さな問題に分割して解決している.
Fibonacci(4)を求める大きな問題は,Fibonacci(3)を求めることと,Fibonacci(2)を求めることの小さな問題に分けられる.

def fibo(int n):
  if (n<=2):
    return 1
  if (mem[n]==0):
    mem[n] = fibo(n-1) + fibo(n-2)
  return mem[n]

BOTTOM-UP
DPテーブルは、TOP-DOWNの下から上への解題方式とは異なる
つまり、小さな問題から、小さな問題を積み重ねて、大きな問題を解決するということです.

def fibo(int n):
  fiboData[0] = 0
  fiboData[1] = 1
  for (int i=2; i<=n; i++):
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2]
  return fiboData[n]

メリットとデメリット

👍長所

の最適な年を見つけることができます.

👎短所

すべての方法が見つかったので、遅い

1.参考資料
2.参考資料
3.参考資料