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

入る前に.
動的計画法は数学者のリチャード・ベルマンが1940年代に使用した用語である.
大きな問題にネストされた小さな問題を解決するための「ダイナミックプランニング法」と呼ばれています.
ベルの自伝で見つけられるから、「ダイナミックプランニング」と「ダイナミック」の2つの言葉に何のつながりがあるのか、ずっと知りたいと思っていました.
アルゴリズムの「時変性と多段階性」特性を体現するために,「動的」という言葉を採用した.
どうてきけいかくほう
動的計画は,ベルマンが定義したように,大規模な問題に小さな問題を重畳する方法である.
従って,動的計画法を用いて問題を解決する核心は문제를 일반화 하는 것である.
とにかく、
ダイナミックプランニング(Dynamic Programming)は、大きな問題を小さな問題に分け、小さな問題で問題を一般化して問題全体を解決する方法です.
問題解決の鍵
小さな問題の一般化とは何ですか.と質問すると
答えは簡単です.これは再帰構造に使用できる점화식である.
数学の中で問題を一般化する時、점화식を求めます.プログラミングでは,この方法で点火式を解き,問題を一般化することもできる.
例:フィボナッチ数列

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

通常、フィボナッチ数列を求める関数は以下のようになります.
解fib(4)が要求される場合、以下のように計算される.
fib(4)
fib(3) + fib(2)
(fib(2) + fib(1)) + (fib(1) + fib(0))
3番目の計算ではfib(1)が2回計算され,計算時間が増加する.
fib(n)中のnが40より大きい場合、計算時間は幾何級数的に増加する.
考えてみれば、fib(40)を救うためには、数回もfib(3)を呼び出す必要がある.これが時間の無駄だ.
ここに注釈が必要です.
注記構造
注記関数の値を計算し、計算値を配列に保存する方法です.必要に応じて関数を呼び出すことなく、配列内の値をすばやく入力できます.
再びボナッチに戻り、計算したfib(3)の値を配列に格納すれば、fib(3)を呼び出すことなくfib(3)の値を取得することができる.
すなわち,f(n)を求めるにはO(n)の時間が必要である.
計算しても計算しない.
これにより、トラブルシューティング時間が大幅に短縮されます.
参考資料
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
https://medium.com/@wooder2050/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0
https://velog.io/@chelsea/1-動的計画動的計画-DP
https://blog.naver.com/kks227/220777103650