2022.03.19 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