[Algorithm] Dynamic Programming

6383 ワード
algorithm テキストリンク
ダイナミックプランニング(Dynamic Programming):ある範囲の答えを解くときに、サブ問題の解決策を計算し、これらの値を保存して、後で同じ問題が発生したときに取り出して使用します.

ダイナミックプランニング法の成立条件


1.Subproblemを重ねる(一部の問題を繰り返す)


ある問題が複数の部分に分かれていると、同じ問題が繰り返されます.

2.最適局所構造（Optimal Substructure）


いくつかの問題の最適な解決策は、一部の問題の解決策として設計できます.

Memoization(コメント作成)


正解を保存し、同じ問題に対して不要な演算を避ける

実施方法


1. Top-Down


最大の質問にアクセスし、小さな質問を呼び出して答えを検索します.
通常は再帰呼び出しによって実現される
m = [0, 1]
function fib(n)
 if n not in keys(m)
  m[n] := fib(n-1) + fib(n-2)
 return m[n]

2. Bottom-Up


最小の問題から答えを探し、問題全体の答えを見つけます.
通常は繰り返し文で実現されます
m = [0, 1]
function fib(n)
  for (i = 2; i <= n; i++)
    m[i] = m[i - 1] + m[i - 2]
 return m[n]

動作時間差

  • DP-時間複雑度:O(n)
  • の典型的なフィボナッチ数列関数−時間複雑度:O(2^2/n)
    • let start;
let end;
start = new Date();
console.log(fiboWithDP(50));
end = new Date();
console.log(end - start, "ms");

start = new Date();
console.log(fibo(50));
end = new Date();
console.log(end - start, "ms");
    12586269025
9 ms
12586269025
110917 ms
    ファイルのダウンロード時-ファイル名の変更
    アルバコン開発日記-Day 03