ダイナミックプログラミング

ダイナミックプランニング(=ダイナミックプランニング)

:再計算を回避するために、計算された結果を別のメモリ領域に保存する方法.時間効率を大幅に向上させる.

データ構造では、ダイナミックとは何ですか?
:プログラム実行中に実行に必要なメモリを割り当てる方法
(でもここでは何の意味もありません)

いつ使えますか.
1.最適な局所構造
:大きな問題を小さな問題に分けて、小さな問題の答えを集中して大きな問題を解決することができます.→ある問題に対する解が最適である場合,その解を構成する部分問題の解も最適である.
2.重複する部分的な問題
:同じ小さな問題を繰り返し解決する必要がある場合

フィボナッチ数列

点火式:a=an,1+an,2 a 1=1 a n=a n=a{n-1}+a n-2}quada 1=1,a_2=1an​=an−1​+an−2​a1​=1,a2​=1

def fibo(x):
  if x==1 or x==2:
    return 1 
  return fibo(x-1) + fibo(x-2)

→fibo(6)の計算プロセスを描画します.

時間複雑度:O(N 2)O(N^2)O(N 2)

f(2)複数回呼び出し、時間を無駄にする.

注記構造

:1回の計算結果をメモリ領域に書き込む方法.同じ問題を再度呼び出すと、コメントの結果が得られます.(=キャッシュ、キャッシュ)
ダイナミックプログラミングに限らず

タワー/厚め

動的プログラミングの典型的な形式は、基準上昇

である.

DPテーブル:結果を保存するためのリスト

上から下へ

d = [0]*100
def fibo_top(x):
  if x==1 or x==2:
    return 1
  if d[x]!=0:
	return d[x] 
  d[x] = fibo(x-1) + fibo(x-2)
  return d[x]

きどうモード

d=[0]*100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n-1):
	d[i] = d[i-1] + d[i-2]
print(d[n])

→コメント作成方法を使用した計算プロセス

時間の複雑さはO(N)O(N)O(N)に減少した.

ダイナミックプログラミングvs分割征服

の一部の問題の重複には違いがある.

動的プログラミング問題の各部分の問題は相互に影響し、一部の問題は

を繰り返す.

分割征服は同じ部分の問題を繰り返し計算しない.

分割征服例:クイックソート

Pivotが位置すると、その基準要素の位置が変わる→Pivotの一部の問題X

を再処理する.

符号化試験の比較方法

👀 与えられた問題を把握することはダイナミックプログラミングのタイプが重要です!
Griddy,実装,完全ナビゲーションなどの考え方で問題を解決できるかどうかを検討し,解決策が思いつかなければ動的に考えてみる.
まず,再帰関数を用いて非効率な完全なナビゲーションプログラムを記述する.
→小問題で求めた答えは大問題でそのまま使えますか?
→コード改善
普通のコットに対処するために、基本的なタイプだけを熟知しても大丈夫です.

cf.最長経路問題

図の中で2つの頂点の最長の経路の問題

を求めます

A~Dの最長経路は[A,C,B,D]であり、A~Cの最長経路は[A,C]ではない.

従って,これらの問題は動的プログラミングで解決することは困難である.