動的計画(DP)
Dynamic Programming
再帰呼び出しとコメントの作成
フィボナッチ数列
フィボナッチ数の再帰関数を求めます
fibo(n)
if n < 2
return n;
else
return fibo(n-1) + fibo(n-2);では、重複を避ける方法はありますか?
アノテーション
アノテーションメソッドを使用したフィボナッチ
memoに配列を割り当て、すべて0に初期化します.
memo[0]を0に初期化し、memo[1]を1に初期化する
fibo1(n)
IF n >= 2 AND memo[n] = 0
memo[n] = fibo1(n-1) + fibo1(n-2)
return memo[n]どうてきけいかくほう
ダイナミックプランニング(Dynamic Programming)は、GRADYアルゴリズムのような最適化問題を解決するアルゴリズムである.
じょうちょうもんだいこうぞう
さいてきローカルもんだいこうぞう
分割征服VSダイナミックプランニング法
分割征服
DP
DPは局所問題の間に依存関係がある
分割征服はトップダウン方式,DPはアップ方式を採用する
DPを適用して、3段階に分けます
最適な海構造の特性を理解する
最適解の値の再定義
アップメソッドを使用して最適解の値を計算する
フィボナッチ数DPの適用
fibo_dp(n)
f[0] = 0
f[1] = 1
for i in 2 -> n
f[i] = f[i-1] + f[i-2]
return f[n]再帰アルゴリズムとは異なり,繰返し計算は行われなかった.繰り返し文が使用されているため、関数呼び出しがX
小銭をさがす
私は1元、4元、6元の硬貨を持っていますが、8元を探す必要があるときは、少なくともいくつかの硬貨を探したほうがいいですか?
非常に近い:6元、1元、1元
ベスト:4元、4元
アップアクセス
にこうけいすうを求める
にこうていり
ダイナミックプランニング法による二項係数計算
bino(n, k)
B[][]
for i in 0 -> n
for j in 0 -> minimum(i, k)
if j=0 OR j=1
B[i][j] = 1
else
B[i][j] = B[i-1][j-1] + B[i-1][j]
return B[n][k]0/1 Knapsack
DPアクセスの使用
リュックの問題の部分を見つけるために、条件を見てみると
ここで、物と物の重量は局所的な問題を定義するために必要である.
リュックが空いていることから、荷物を一つずつリュックに入れることと入れないことは、今リュックに入っているものの価値の和によって決まるからです.
また、リュックサックに荷物を入れるときは、リュックサックの容量が基準を超えているかどうかをチェックします.
したがって,リュックサック問題の一部の問題は以下のように定義できる.
K[i,w]を再帰的に表す
for i in 0 -> n : k[i, 0] = 0
for w in 0 -> w : k[0, w] = 0
for i in 1 - > n
for w in 1 -> w
if wi > w
K[i, w] = K[i-1, w]
else
K[i, w] = max(vi + K[i-1, w - wi], K[i-1, w])
return K[n, W]Reference
この問題について(動的計画(DP)), 我々は、より多くの情報をここで見つけました https://velog.io/@mingggkeee/동적-계획법DPテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol