DP & Divide and Conquer

1.定義

動的計画法

小部分故障排除この部分問題の解決方法を入力、大部分問題

を解決する.

トップダウンメソッド最低答えから上

へ

Memorizationテクノロジー:以前に計算された値の再計算を避ける

例)フィボナッチ数列

分割征服

問題をいくつかの解に分解し、1つの解に統合するアルゴリズム.

の下のスプライン法を用いて位相解を解く

は通常、再帰関数を用いて

を実現する.

問題を細分化する場合、一部の問題は重複しない

例:連結ソート・クイック・ソート

2.異同

共通点

の問題を最小のユニット

に分割する.

差異

動的計画法

の一部の問題は重複しており、親の問題を解決する際に

を繰り返し使用する.

記憶法

を用いる.

分割征服

一部の問題は互いに重複しない

を使用しない記憶法

3.動的計画アルゴリズムの理解

フィボナッチ数列

→重複値を計算せずに保存~

再帰呼び出しの使用

def fibo(num):
	if num<= 1:
		return num
	return fibo(num-1) +fibo(num-2)

fibo(4) → fibo(3)+fibo(2) →fibo(2) +fibo(1)....
同じものが何度も運行されます.

Dynamic programming

def fibo_dp(num):
	cache = [O for index in range(num+1)]
	cache[0] = 0
	cache[1] = 1
	
	for index in range(2,num+1):
		cache[index] = cache[index-1] +cache[index-2]
	return cache[num];