動態規劃法 Dynamic programming ; DP，它與分治法很像，都是將大問題分割成小問題，而它和分治法不同的地方在於，它會將處理過的子問題解答，將它記憶起來，為了避免重複的計算。

費波那西數列

最簡單說明動態規畫法的問題就是費波那西數列，它的定義如下。

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2

也就是說F2所代表的意思為F2 = F1 + F0，也就等於F2 = 1 + 0。

我們直接來看程式碼，首先先看沒有用cache的費波那西數列。非常的簡單就只用遞迴來計算每個數列的值。

function fib (n){
	if(n<=1){
		return n;
	}
	return fib(n-1)+fib(n-2);
}

我們這邊使用個例子，來說明它的計算流程，我們執行fib(5)，然後我們直接看下面這張圖來了解它的過程，首先是項點fib(5)，它就是由fib(4)、fib(3)組成，然後再將之分解，就會如下圖的結果。其中我們有用綠色底來上色的地方，它就代表我們有重複的數字，像fib(2)就被計算了3次，所以上面這個演算法事實上做了很多重複的事情。

而接下來，我們就將它改良一下，也就是用動態規畫法的概念下修改而成，它每次計算過一個數字後，就會先存起來，然後有需要時，就在將它拿出來。

程式碼如下，它會將每個有計算過的數列儲放在記憶體內，有用到它時，就將它拿出來用。 下面就是簡單的使用動態規畫法概念實作的費波南西數列。

//有用Cache
var memo = [];
var count = 0;
var fib_cache = function(n){
	if(n <=1){
		return n;
	}

	if( typeof memo[n] !== 'undefined'){
		return memo[n];
	}else{
		memo[n] = fib_cache(n-1) + fib_cache(n-2);
		return memo[n];
	}
}

背包問題（Knapsack Problem）

這個問題的定義如下。

假設一個背包最多放10公斤的物品，要如選擇那些物品，才可以使背包的總價值最高呢?

這個問題我們事實上有很多解法，我們也可以用之前學的貪婪法來解，但我們這篇文章將要用動態規畫法來解決這問題。

要解決這個問題，我們的演算法邏輯如下。

• 當物品重量大於限制重量時，該物品不放入，進行下個物品的比較。
• 當物品重量小於限制重量時，考慮兩種狀況 (1) 將該商品放入後的情況 (2) 不將該商品放入後的情況。再取兩者間最大的價值。

我們簡單的用例子來說明一下。

假設可選擇物品如下。並且限重量為3。

然後我們看看下圖的執行流程，首先我們先看最上面長方形，先不要看紅色的數字，先看(3)，這代表這限重量，就是我們最多可以選擇的產品，然後我們會開始跑上面有提到的演算法邏輯的流程。

注意在開始前，先不要看紅紅的方塊。

首先我們會先將產品 A ，拿來決定要不要選擇，產品A重量(2)小於限制重量3，可以選擇，但要不要選呢 ? 我們要考慮兩種狀況的後果 (1) 不選擇產品 A (2) 選擇產品 A ，接下來，下圖左邊的分支，就是如果選擇第一種情況會如何。

我們先來看不選擇產品A的情況，因為它有沒有拿產品A，所以限重還是一樣(3)，接下來這邊也要考慮兩種情況 (1) 不選擇產品 B (2) 選擇產品 B，由於後面沒有可選擇，所以就不需要在往下深入，直接在這層決定要選B，還是不選B ; 因為不選擇產品B總價值為0而選擇產品B的總價值為2因此，這層我們選擇產品B，也就是左邊不選擇產品A上面紅色塊塊的價值。

然後我們在來看右手邊，一開始選擇產品A這分支，因為它選擇了A，所以限重量只剩(1)，所以這邊我們不沒辦法在選B，所以這層的總價值為3。

最後我們在來看決定要選擇 A還是選擇B，上述的流程都已經計算出這兩個選項的結果，因此我們選擇選擇產品A這個結果(3>2)。

接下來我們來實作程式碼。

debugger;
var items = [{
	w: 2,
	v: 3
}, {
	w: 1,
	v: 2
}, {
	w: 3,
	v: 4
}, {
	w: 2,
	v: 2
}];

function Array2DVar(x, y) { // 定義二維陣列原型
	this.length = x;
	this.x = x; // x 維度長度
	this.y = y; // y 維度長度
	for (var i = 0; i < this.length; i++) // 建立個元素陣列
		this[i] = new Array(y); // this 代表物件本身
}
var temp = new Array2DVar(5,5);

function dpProcess(items, index, weight) {
	if (temp[index][weight] != null) {
		return temp[index][weight];
	}

	var result = 0;
	if (items.length == index) {
		result = 0;
	} else if (items[index].w > weight) {
		result = dpProcess(items, index + 1, weight);
	} else {
		result = Math.max(dpProcess(items, index + 1, weight), dpProcess(items, index + 1, weight - items[index].w) + items[index].v);
	}

	temp[index][weight] = result;
	return result;
}

console.log(dpProcess(items, 0, 5));

其中下面這段程式碼，是要產生一個矩陣，用來存放我們曾經計算過的值，當然也不一定要用矩陣，只要可以存放就好，至於為什麼這裡要用矩陣等等會說明。

function Array2DVar(x, y) { // 定義二維陣列原型
	this.length = x;
	this.x = x; // x 維度長度
	this.y = y; // y 維度長度
	for (var i = 0; i < this.length; i++) // 建立個元素陣列
		this[i] = new Array(y); // this 代表物件本身
}
var temp = new Array2DVar(5,5);

然後下面這段程式碼是判斷，如果有已經計算過的值，則直接從記憶體取出。

	if (temp[index][weight] != null) {
		return temp[index][weight];
	}

接下來這段是重點，它有三個區塊，首先第一個區塊，當items.length == index時，也就代表這，它已經沒有item可以繼續選擇下去了，再來第二個區塊，這塊是在說明如果某產品的重量大於剩於限重量，則往下一個產品繼續選擇，再來最後一個區塊就是我們上面所提到的過程，如下，它會將狀況分成兩種，然後再深入的去選擇。

當物品重量小於限制重量時，考慮兩種狀況 (1) 將該商品放入後的情況 (2) 不將該商品放入後的情況。再取兩者間最大的價值。

	if (items.length == index) {
		result = 0;
	} else if (items[index].w > weight) {
		result = dpProcess(items, index + 1, weight);
	} else {
		result = Math.max(dpProcess(items, index + 1, weight), dpProcess(items, index + 1, weight - items[index].w) + items[index].v);
	}