フィボナッチ数列

DP

動的プランニング-動的プランニング(名前と論理はまったく関係ありません)😅)
問題を分けて小さな問題の答えを求め、それを使ってもっと大きな問題の答えを求める方法.

分割征服に似た感覚

点火式を求め、再帰文または繰り返し文によって

を実現する.

タイプ1)フィボナッチ数列

f(0)  = 0
f(1) = 1
f(n) = f(n-1) + f(n+2)

再帰関数または繰り返し文で解くことができます.

注釈

耳で解くと.
すでに求められた値にまた求める必要がある問題が発生した.
したがって,求めた値を保存して問題を解決する必要がある.(キャッシュ、コメント作成)
その結果、以下のように、以前に求めた値を取り出して用いることができるので、繰り返しの演算(求めた値)を行う必要がなく、演算速度を向上させることができる.

DP実施方法

top-downBottom-up复句注今この时间帯をメモして、それから必要なものをすべて引き出して、使うのはとても直感的で、コードの毒性はとても良くて、时间とメモリを节约することができて、再帰関数を何度も呼び出すことができて、だからDP表の充填の顺番を知る必要があります.
pythonの場合、言語自体が遅いため、この2つの場合、特定の方法でしか解くことができない場合があります.
C++言語自体はすぐに、どちらの言語も使用できます
ただし、DPテーブルの塗り順が分かればBoottom-Upの方が便利です

タイプ2)二項係数

bino(n,0) = 1
bino(n,n) = 1
bino(n,r) = bino(n-1, r-1) + bino(n-1, r)