簡介

Dynamic Programming中文譯作動態規劃,動態規劃類似Divide and Conquer,一個問題的答案來相依於子問題,常用來解決最佳解的問題。與Divide and Conquer不同的地方在於,動態規劃多使用了memoization的機制,將處理過的子問題答案記錄下來,避免重複計算,因此在子問題重疊的時候應該使用動態規劃;Divide and Conquer通常使用遞迴(Top-Down)來處理,轉成迭代法(Bottom-up)來解並不容易,故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。

同樣拿費波那西數列(Fibonacci)為例子

lect3-9

使用Divide and Conquer的寫法如下:

function Fibonacci(n)
	if n == 0
		return 0
	if n == 1
		return 1
	return Fibonacci(n - 1) + Fibonacci(n - 2)

如同之前在Divide and conquer一文中所說,會重覆計算黃色和綠色的部分,而改用動態規劃寫法如下:

var map // cache of fibonacci
function Fibonacci(n)
	var value = map[n]
	if value == null
		if n == 0
			value = 0
		else if n == 1
			value = 1
		else
			value = Fibonacci(n - 1) + Fibonacci(n - 2)
		map[n] = value 
	return value

結果在綠色部分就會因為有Cache資料而不必計算,也不會在往下遞迴,而達到增進效能的目的。另外也可以直接將n=0和n=1的資料事先放入Cache中:

var map // cache of fibonacci
map[0] = 0
map[1] = 1
function Fibonacci(n)
	if map[n] == null
		map[n] = Fibonacci(n - 1) + Fibonacci(n - 2)
	return map[n]

 

相關範例

費波那西數列(Fibonacci)

巴斯卡三角形(Pascal's Triangle)

上下樓梯問題&(籃球)得分問題

最大子序列(Maximum Subarray)

最短路徑(Shortest paths)

...

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()