2022.03.19 TIL

3752 ワード
python TIL テキストリンク
ダイナミックプランニング法について

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

  • 入力サイズの小さい問題を解決し、保存し、対応する値で大きな問題を解決する方法を選択します.
  • アルゴリズムではなく、問題を解決する方法です.
  • 動的計画法の方法論は以下の2つに分けられる.

  • マーク
    上向きの方法でサブ問題を事前に計算し、サブ問題を利用して親問題を解決する方法.一般的な動的計画法はトポロジーメソッド論を指す.

  • コメントの作成
    上から下への方法で大きな問題をサブ問題に分けて処理し,問題を解決した後に対応する値を保存する.DPでは、サブ質問の答えは毎回同じであるため、保存した値を読み込んで使用することができる.
    • 似たような分割征服手法がある.
    分割征服は問題を細分化し,それぞれ解いてから統合する方式であり,上から下への方法を採用する.
    この場合、一部の問題は繰り返されません.(クイックソート、グレースケールなど)
    動的計画法の代表的な例はフィボナッチ数列である.

    フィボナッチ数列

  • 再帰的用法を用いて実現されたフィボナッチ数列
    • def fibo(n):
	if n <=1 :
		return n
	return fibo(n - 1) + fibo(n - 2)
  • 動的計画法を用いて実現されたフィボナッチ数列
    • def fibo_dp(n):
	# 저장공간을 먼저 만들어야 한다.
	dp = [0 for i in range(n + 1)]
	dp[0] = 0
	dp[1] = 1

	for idx in range(2, n + 1):
    	# 저장
		dp[idx] = dp[index - 1] + dp[index - 2]
	return dp[n]
    ソース
    https://hongl.tistory.com/20
    セロリとREDISでDjangoを展開すること
    Phpmyadmin学習