ご存知ですか자료구조 삼대장
左から右へダイナミックプログラミング、DFS(深度優先ナビゲーション)、BackTracking
これは私が勝手に決めた三隊長です.誤解しないでほしい
毎日の資料構造を学ぶ過程で、上に現れた三大将の一人が現れた.
ダイナミックプログラミング、(キュウリのやつは私たちの中で一番弱い!)
見ているYouTubeカリキュラムコードのないプログラミング勉強ですが、この資料の構造の目的や原理についての議論が不足しているため、数学の公式を書くように書いてあり、「ああ、難しいな、なんて思う」だけで終わってしまい、何がダイナミックプログラミングなのか整理するためです.
コメントでエラーメッセージをフィードバックすることをいつでも歓迎します.

きれいな名前に隠された原理

「ダイナミックプログラミング」という名前から、この資料構造がどのような原理で計算されているのかを推定するのは難しい.動的プログラミングとは何の関係もないので,推理が困難なのは当然である.

ではDynamic番組は...という思いでDynamicプログラムを学びましたが、Dynamicプログラムの名前はDynamicプログラムの名前より1)기억하며 풀기という名前の方がふさわしいという結論に至りました.
私がDPを解いたときに思いついた2つのキーワードは、SubProblem(문제 쪼개기)、Memoization(기억해두기)2)

フィボナッチ数列の例

フィボナッチ数列は1,1,2,3,5,8...f(n)=f(n-1)+f(n-2)を満たす点火式の数列を表す.ここで使用可能점화식行いSubProblem(문제 쪼개기)

fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) when n > 1

fが1つの再帰関数であると考えると、f(2)を求めるために、f(0)とf(1)の戻り値を利用してもよいし、算出した値を利用してf(3)=f(2)+f(1)を計算してもよい.
しかし、私たちの기억하며 풀기方法はここまでで非常に非効率です.
2)

上図に示すように、fib(5)を再帰的に解くとfib(1)関数が5回呼び出される.そこで、コアな方法はfib(1)の答えを別の場所で覚えて、それを書くこと다시 계산을 하지않고.
subProblemの答えを覚えるため、ほとんどのdpは答えを配列に格納し、削除します.

top-downとbottom-up

ここから方法論の説明です.

top-down

実施部分で最も混乱している部分はtop-down部分である.

const fib_dp = (n) => {
  if(n>2){
    fib_dp(n-1) + fib_dp(n-2)
  }else{
   return 1 
  }
}

トップダウンを実施する過程で,メモリ割り当てがコアであることを忘れ,再帰を努力しすぎたため,繰返し計算の誤りを犯しやすい.(時間が非常に複雑になりました…)
したがって,top-downメソッドでは,覚えながら解くことが重要であり,top-downでは関数自体が保存される.
例えば、fib(5)=fib(4)+fib(3)が下を向くようになると、fib(4) + fib(3)それ自体がarr[5]に格納され、以降fib(1)が呼び出されて全て計算される.

const fib_array = [0,1];
const fib_dp = (n) => {
if (n < fib_array.length) return fib_array[n]
else {
   const fib = fib_dp(n-1) + fib_dp(n-2)
   fib_array.push(fib)
   return fib
}
}

bottom-up

その名の通り、床から上がってきたのです.小さな問題から始め、小さな問題を徐々に蓄積し、大きな問題を解決することです.計算fib(1)+fib(0)=fib(2)は、fib(2)をdb配列に保存し、答えがdb配列に格納されているサブ問題であれば、fib(3)=db[2]+db[1]に直接インポートして計算する.
数値を記憶し続ける必要がある空間の代わりにO(n)の時間的複雑さを用いることができる.

const fib_dp_bottom = (n) => {
    if (n===0) return 0;
    else if(n===1)return 1;
    let fib_array = [0,1];
     for(let i =2; i<n+1; i++){
        fib_array.push(fib_array[i-1] + fib_array[i-2])
     }
     return fib_array[n]
    }

整理する

ダイナミックプログラミングは,問題をサブ問題に分割し,サブ問題を保存して繰返し計算を回避する資料構築方法である.

実際、コードテストの問題が使えるかどうか分かりません.本当の数学の問題のように、問題ごとにいろいろな考えがあって、考えにくいです.賢い人だけが使える資料構造だという人もいます.簡単な質問で何度も経験すると、コツがあるかもしれません.

1)李光根教授の著書『コンピュータ科学が開く世界』では,動的プログラミングの本質的意義に翻訳を加えると.
2)出所:『Pythonアルゴリズムインタビュー』