【DP1】鋼條分割詳解

[DP]
原文再續書接上一回，上一篇文章的背包講的有點過于狹隘，我就某一類問題解釋一種演算法的思想：動態規劃(Dynamic Programming)，簡稱DP，
我們在生活中不免會遇到一類問題，求什么什么的最大，什么什么的最小，在這類問題中，如果有演算法基礎的同學可能會知道貪心演算法，但是貪心演算法是無法在所有的情況下保證最優解的，而DP是可以的，
那么DP是什么？我們直接用一道題目來舉例子去解釋DP，
這里采用的例子參考自CLRS中的鋼條分割問題，我只做一個概括性復述，有興趣的同學可以去看看原著（這里強力吹一波CLRS，如果能夠靜下心來看，這本書還是相當的不錯，）
長度為n英寸的鋼條，若給出一個陣列p[n]，該陣列是指不同長度下鋼條所能給出的價格，例如：

有一種很蠢但是很好理解的演算法，就是我一共有n個元素(長度為n的鋼條分割最小單元為1的情況下，我最多有n個元素)，所以我一共有2^(n-1)個方案（含重復的）我每個方案都算一個價格出來，在其中取最大值不就可以了嗎？
當然可以，但是開銷也是蹭蹭蹭地往上跑，

我們先提出一種遞回的解法，
我們來分析最初的情況，我們從最左端開始看
我們在一開始，在i=1的情況下，我們可以選擇切/不切
注意：這里是整個演算法的關鍵
如圖：

我們把情況變成正常情況，

我們就有，在k處，選擇切還是不選擇切，設，我們的最優解一共把他切成了K段，那我們就有利潤=P[I1] +P[I2] +P[I3]+…+P[Ik]我們這里的I k指的是第k段的長度，
我們光這樣看好像覺得有點不知所措，我怎么知道他在哪切的？我怎么知道為什么這樣切就是最優解？
那我們就來求這個切的位置
我們的基礎方法就是把我們每次的切點，都表示，我要將左邊單獨看成一段，也就是說，我在這里切了，左邊的長度就是我賣出去鋼條的長度，那么在此基礎上，我們就有：
我只需要比較切了跟不切的大小就可了，我在切/不切之間取最大值，我們就知道了，
打個比方，我最初我要比較i=1的時候我在想要不要切，那我們切不切的標準是為了讓我們最后的值是最優解嘛，那很簡單，我直接比較我切的時候和不切的時候哪個值更大不就完了？
遞回代碼如下

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n) {
	if (n == 0)return 0;
	int q = -1;
	for (int i = 1; i <= n; i++) {
		q = max(q, valuesTable[i] + value(valuesTable, n - i));
	}
	return q;
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input

		cout << "Output is " << value(valuesTable, lengthOfSteel)<<endl;
	}
}

當我們用max_values_length表示這個長度能拿到的最大利益時，我們就有一個推導方程，（不是什么高深的公式，就是從上述推匯出來的結論)
我們這里的關鍵在于

q = max(q, valuesTable[i] + value(valuesTable, n - i));

我們把鋼鐵剩余部分的價值（減去前i長度后的長度的價值）交給遞回的程式去計算，我們不需要手動去算，這就是遞回代碼的優勢–容易理解，且容易實作，
可是
這一段代碼不比我們一開始羅列出所有的方案，然后找最大值要好，為什么？我們畫樹狀圖進行分析

我們從樹狀圖中可以看到，在這樣遞回的運算中，我們每一次求第n項，必須訪問1到n-項，就是說，第n項的值取決于前n-1項的值，而在這個程序中，我們會反復求解于底層的某一個數，例如在該圖中，1就被訪問了3次（圖中只畫出了三次，但其實2擴展之后還會再訪問一次了），也就是說0會被訪問很多次，

這樣其實增加了很多的開銷，我們DP的思想就是在遞回程式中每次取值的時候我們都能有一個地址，讓我能夠判斷這個值是否被算過，如果被算過了那么我們就直接呼叫就可以了，而不是像傳統的遞回程式需要重新計算一次，如果沒算過，那就算一次之后進行存盤就好了，以便下一次呼叫的時候能夠直接通過DP_Table陣列進行訪問就可以了(DP_Table就是一個動態規劃表，用來存盤每一個狀態的值，避免過度的運算)

我們先實作自頂向下的帶備忘的遞回寫法，

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n,int DP_Table[]) {
	if (DP_Table[n] >= 0)return DP_Table[n];
	else {
		int temp = -1;
		for (int i = 1; i  <= n; i++) {
			temp = max(temp, valuesTable[i] + value(valuesTable, n - i, DP_Table));
		}
		DP_Table[n] = temp;
		return temp;
	}
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		int* DP_table = new int[lengthOfSteel + 1];
		memset(DP_table, -1, lengthOfSteel + 1);
		DP_table[0] = 0;
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input

		cout << "Output is " << value(valuesTable, lengthOfSteel,DP_table)<<endl;
	}
}

如果此時你理解了不帶備忘效果的遞回代碼，那么我相信這段代碼你看起來也不會吃力，

盡管帶備忘效果的遞回代碼已經能夠滿足我們的時間復雜度的要求了，但是我們的計算機是非常不愿意跑你的遞回代碼的，當n的數量級上去了，壓堆疊的時間也不能忽略，還有可能會發生把堆疊壓爆而非正常終止的情況，那么我們就順順計算機的意愿：寫一個自底向上的迭代程式就能避免這方面的問題了，
為了方便理解，我先貼代碼再解釋

#include<iostream>
using namespace std;
int max(int a, int b) {
	return a > b ? a : b;
}
int value(int valuesTable[], int n,int DP_Table[]) {
	DP_Table[0] = 0;
	int temp = -1;
	for (int i = 1; i <= n; i++) {
		temp = -1;
		for (int j = 1; j <= i; j++) {
			temp = max(temp, valuesTable[j] + DP_Table[i - j]);
		}
		DP_Table[i] = temp;
	}
	return DP_Table[n];
}
int main() {
	int lengthOfSteel;
	while (cin >> lengthOfSteel) {
		int* valuesTable;
		valuesTable = new int[lengthOfSteel + 1];
		int* DP_table = new int[lengthOfSteel + 1];
		for (int count = 1; count <= lengthOfSteel; count++)cin >> valuesTable[count];
		//input
		cout << value(valuesTable, lengthOfSteel, DP_table)<<endl;
		
	}
}

主函式中的代碼就沒什么好說了，就都是一個呼叫Solution的程序，這里主要說一下value函式
在Value函式中，我每一次的回圈開始我都定義一個臨時變數temp，用來記錄該切點左邊一段的鋼條能賣最貴是多少，并把它放在DP陣列的對應索引下，而我們每次在最外層回圈結束，都能依次得到，前面長度為i的鋼條最貴能賣多少錢，而我們后面的最優解又只依賴著前面的各個最優解的值（注意這里的只，這決定了沒有后效性的問題，后文會對后效性進行詳解），所以就能算出整體的最優解，因為我們能保證每一個區域都是最優解，自然出來的結果也是最優解

好了，我們三段代碼，三種方法解決了這個鋼條切割的問題，我們來總結一下吧，我們解決問題的順序依次是，我們要找到一個能夠解決該問題的遞回代碼，而該遞回代碼依賴著我們的分段分析，這也稱為最優子結構，在鋼條切割問題上，我們的最優子結構就是，我們要不要切，我們切了之后是分成兩段多長的鋼條，對于切下來的部分可以直接轉換成價值，而剩下的鋼條可以重新看成一個新的鋼條切割問題，只是此時的sum不再是0，長度變成n-i，轉換成偽碼的形式就是

CUT-ROD(p,n)
	if(n==0)
		return 0
	for(i =1 -> n)
		q=max { q,p[i]+CUT-ROD(p,n-i) }
	return q;

而在這個鋼條分割問題中，我們顯然發現他們除了存在一種最優子結構以外，還會因為遞回的代碼而產生一種重疊子問題(Overlapped Subproblem)，而順口提一嘴上面提到的無后效性，這直接決定了我們能不能用動態規劃演算法求解某問題，如果一個問題不存在無后效性，例如我們圖論方面的部分問題，
在我后續關于DP的文章中還會多次重復地提到
1.重疊子問題
2.無后效性
3.最優子結構
這三者，

感謝你能看到這里，