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

1つの問題だけを解くアルゴリズム。

通常、多くの分割征服技術の欠点は、同じ問題を再解決することである.単純な分割征服によって問題を解決すれば,深刻な効率低下を招く.

動的プログラミング方法と条件

方法

:すべての小さな問題は1回の問題を解くだけなので、答えを見つけた小さな問題がある場所に現れ、別の大きな問題が現れた場合は、前の注釈の小さな問題の結果値を使用してください.

条件:大きな問題を小さな問題に分ける.
小さな質問で求めた答えは、それを含む大きな質問でも同じです.

計算結果をアレイに保存するには、コメント(Memoization)を使用し、後で同じ計算を行う必要がある場合は、保存した値を返すだけで問題を解決します。

フィボナッチ数列

フィボナッチ数列を例にとると、フィボナッチは1,1,2,3,5, ...の数に達する.すなわち,次の数列値=前の数列+前の2ステップ数の和となる.

条件小さな問題が繰り返される。

フィボナッチ数列の5番目の値を求めるには、3番目と4番目の値が必要です.また、4番目の値を得るには、2番目または3番目の値が必要です.この場合、5番目の値には3番目の値が必要であり、4番目の値にも3番目の値が必要です.

条件同じ質問でも、求めるたびに答えは同じです。

フィボナッチ数列の場合、1番目と2番目の数列は1に固定されるため、3番目の数列の値は常に3になります.4番目の数列は2番目または3番目の値を求めるので、正解は同じです.

フィボナッチ数列の実現(Memoization X)

図示のように出力に問題はないが,フィボナッチ数が増えるにつれて計算機呼び出し関数の回数が2のn次方に増えるので,注釈変換を用いなければならない.

function getFibonacci(n){
  if(n<=2){
    return 1;
  }
  else{
    return getFibonacci(n-1) + getFibonacci(n-2);
  }
}

console.log(getFibonacci(5))

フィボナッチ数列の実現(Memoization O)

図示するように、コード実装で算出された結果は、アレイarrに保存されるため、求められた値は再び求められない.

let arr = [0];
function getFibonacci(n){
  if (n<=2){
    return 1;
  }
  if(!arr[n]){ // 내가 저장한 값 중에 없다면...
    arr[n] = getFibonacci(n-1) + getFibonacci(n-2);
  }
  return arr[n];
}

console.log(getFibonacci(5));