資料結構與算法系列源代碼：https://github.com/ThinerZQ/AllAlgorithmInJava
本文源代碼：https://github.com/ThinerZQ/AllAlgorithmInJava/blob/master/src/main/java/com/zq/algorithm/dynamicprogrammin/SteelBar.java
如果代碼連結失效了，麻煩評論給我。
動态規劃與分治法相似，都是通過組合子問題的解來求解原問題。
分治法将問題劃分為不互相交子問題，遞歸的求解子問題，再将他們組合起來，求出原問題的解。
與之相反，動态規劃應用于子問題重疊的情況，即不同的子問題具有公共的 子子問題。這種情況下分治法會重複的求解那些公共的子子問題。而動态規劃算法對每個子子問題隻求解一次，将其存放在某一個表格中，無需每次求解一個子子問題時都重新計算，避免了不必要的計算工作，特别是當問題規模比較大的時候，在時間上有顯著的差別
動态規劃用來求解最優化問題。這類問題可以有很多可行的解，每個解都有一個值，我們希望需找具有最優值（最大或最小）的解。當然可能同時存在多個最優解（同時最大，或同時最小），動态規劃隻要求找到其中一個就好了。
這裡我們用算法導論裡面的鋼條切割為例子。
切鋼條：假如Serling公司出售一段長度為 i 英寸的鋼條的價格為 pi( i =1,2,3,4…機關問美元)。鋼條的長度為整英寸。
下表是一個價格表。
| 長度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 價格pi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 |
假設Serling公司進了一批長度為10的鋼條，那麼怎麼切割才能使利益最大呢，長度為 9 , 8 呢？
對于上述價格表樣例，我們可以觀察出所有最優收益值Ri及對應的最優解方案：
| 最優值 | 切割方案 |
|---|---|
| R1 = 1 | 切割方案1 = 1（無切割） |
| R2 = 5 | 切割方案2 = 2（無切割） |
| R3 = 8 | 切割方案3 = 3（無切割） |
| R4 = 10 | 切割方案4 = 2 + 2 |
| R5 = 13 | 切割方案5 = 2 + 3 |
| R6 = 17 | 切割方案6 = 6（無切割） |
| R7 = 18 | 切割方案7 = 1 + 6或7 = 2 + 2 + 3 |
| R8 = 22 | 切割方案8 = 2 + 6 |
| R9 = 25 | 切割方案9 = 3 + 6 |
| R10 = 30 | 切割方案10 = 10（無切割） |
更一般地，對于Rn（n >= 1），我們可以用更短的鋼條的最優切割收益來描述它：
Rn = max(Pn, R1 + Rn-1, R2 + Rn-2,…,Rn-1 + R1)
首先将鋼條切割為長度為i和n - i兩段，接着求解這兩段的最優切割收益Ri和Rn - i（每種方案的最優收益為兩段的最優收益之和），由于無法預知哪種方案會獲得最優收益，我們必須考察所有可能的i，選取其中收益最大者。如果直接出售原鋼條會獲得最大收益，我們當然可以選擇不做任何切割。
注意到，為了求解規模為n的原問題，我們先求解形式完全一樣，但是規模更小的子問題。當完成首次切割之後，我們将兩段鋼條看成兩個同等的鋼條切割問題執行個體，通過組合兩個問題的最優解，并在所有可能的兩段切割方案中選擇組合收益最大值，構成原問題的最優解，我們稱這樣的問題滿足最優子結構性質：問題的最優解是由相關子問題的最優解組和而成的，這些子問題可以獨立求解。
分析到這裡，假設現在出售10英寸的鋼條，應該怎麼切割呢？為了友善分析，我們使用鋼條長度=4來分析問題
1、解法：
1.1 遞歸法：
/**
* 遞歸方法，時間複雜度為O（2的N次方），因為考察了 2的N-1次方種可能
* @param p，鋼條的價格數組，
* @param n，鋼條的長度，這裡的劃分是以 1 為機關
* @return 最大收益
*/
public int cut_rod(int[] p,int n){
//遞歸出口，n=0，不用切割了。
if ( n==){
System.out.println("調用子問題規模：0");
return ;
}
// q 是最大值，初始值設為為一個負值，
int q=-;
//對于每一次遞歸調用，都會求1..n之間的最優質，然後傳回給上一層
for (int i=;i<=n;i++){
//目前長度為 n 的切割收益的最大值，是目前的 q .和p[i]+cut_rod(p,n-i)中的最大值，循環中時不斷改變q值的，
System.out.println("調用子問題規模："+n);
q=max(q,p[i]+cut_rod(p,n-i));
if (i==n){
System.out.println("子問題規模為 "+n+" 的最優值 = "+q);
}
}
System.out.println("回到第："+(n+)+"層");
System.out.println();
return q;
}
public int max(int a,int b){
return a>b?a:b;
}
1.1.1 分析：
上面代碼的遞歸中，始終會重複執行太多相同的操作，例如cut_rod(p,4)會遞歸調用cut_rod(p,3),cut_rod(p,2),cut_rod(p,1),cut_rod(p,0)，當調用cut_rod(p,3) 的時候，又會遞歸調用cut_rod(p,2),…cut_rod(p,1)……..。
1.1.2 程式輸出結果：
1.1.3 程式遞歸分析
………..如此多的重複遞歸是沒有必要的，這也是動态規劃所要處理的問題。
怎麼避免重複調用呢？？
動态規劃的做法是，将每一次求得的cut_rod(p,i)的最優值儲存在一個表（數組）裡面，每次需要使用的時候，不用再遞歸調用了，直接使用就好了。
1.2 動态規劃——>帶備忘的自頂向下法:
/**
* 動态規劃方法
* 帶備忘的自頂向下法
* @param p，鋼條的價格數組，
* @param n，鋼條的長度，這裡的劃分是以 1 為機關
* @return 最大收益
*/
public int memoized_cut_rod(int[] p,int n){
//一個數組，用r[i] 來儲存 鋼條長度為 i 的時候的最優值，初始值賦為 -1.一個負值就行。
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=-;
}
//調用遞歸的那個方法，傳回長度為 n的最優值。
return memoized_cut_aux(p,n,r);
}
/**
*
* @param p，鋼條的價格數組，
* @param n，鋼條的長度，這裡的劃分是以 1 為機關
* @param r 儲存中間值的數組
* @return 最大收益
*/
public int memoized_cut_aux(int[] p,int n,int[] r){
//遞歸出口，如果r[n] >0,表明，長度為 n 的鋼條的最優值已經存在了。不用遞歸了，直接傳回這個最優值，這裡必須是r[n]>=0,因為r[0]是等于0的，
if (r[n]>=){
System.out.println();
System.out.print(" ------直接傳回r[" + n + "] = " + r[n] );
return r[n];
}
//設定零時變量 q 最為最大值
int q=-;
//剛進入遞歸的時候，剛開始一路調用下來，必然是從這個口出去。
if (n==){
q=;
System.out.print(" 調用 n ="+q + " 第一次儲存r[0]的值：" + q);
}else {
//遞歸調用，求解最大值。
System.out.println(" 調用 n ="+n);
for (int i=;i<=n;i++){
q = max(q,p[i]+memoized_cut_aux(p,n-i,r));
System.out.print(" 開始回溯到n="+n);
if (i==n){
System.out.println();
}
// System.out.println();
}
}
System.out.println();
//将每一次求的長度為 n 的最優值儲存在數組 r 裡面
r[n]=q;
//傳回最大值
if (n==r.length-){
System.out.println("程式結束，傳回r["+n+"]="+r[n]);
}
return q;
}
1.2.1 分析：
上面使用自頂向下的方法，求解問題，就像深度優先搜尋二叉樹一樣。具體分析見下圖
1.2.2 程式輸出結果：
1.2.3 程式遞歸分析：
1.3 動态規劃——>自底向上法：
/**
* 動态規劃，自底向上求解。
* @param p，鋼條的價格數組，
* @param n，鋼條的長度，這裡的劃分是以 1 為機關
* @return 最大收益
*/
public int bottomUpCutRod(int[] p,int n){
//一個數組，用r[i] 來儲存 鋼條長度為 i 的時候的最優值，初始值賦為 0.
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=;
}
//循環,外層依次求解 1....n的最優值
for (int j=;j<=n;j++){
int q=-;
//内層，依次在 1 .. j 中求出最大值，
//例如
// 當 j =1 的時候，q=max(q,p[1]+r[0]) .求的r[1]的最優值
// 當 j =2 的時候，q=max(q,p[1]+r[1])，然後再是 q=max(q,p[2]+r[0]) ，求的r[2]的最優值
// ... 以此類推
for (int i=;i<=j;i++){
q=max(q,p[i]+r[j-i]);
}
//記錄 j 的最優值
r[j]=q;
}
//最終傳回 n 的最優值
return r[n];
}
1.3.1 分析：
這個方法是動态規劃最佳方法，具體見後面的總結
1.3.2 程式結果：
1.3.3 程式分析：
自底向上的方法，不必進行遞歸調用，而是直接通路數組元素r[j-i]來獲得規模為j-i的子問題的解。同時也将規模為j的解存入r[j]。就像上圖一樣，r[0]的解是0，r[1]的解依靠r[1] ，r[2]的解依靠r[0]和r[1]…..r[4]的解依靠r[0]和r[1],r[2],和r[3].
上面隻是求出了，鋼條長度為 i 的最優值，那麼怎麼切割呢？下面砸門來看看
1.4 求解切割方案
直接上代碼，
extended_button_up_cut_rod
函數和自底向上求解最優值的函數是一樣的，不同點就是加入了一個儲存切割方案的數組s，每次找到最優值的時候，記錄切割方案。
/**
* 求解最優值群組合方案
* @param p 價格表
* @param n 鋼條長度
* @param r 最優值數組，
* @param s 切割方案數組
*/
public void extended_button_up_cut_rod(int[] p,int n,int[] r,int[] s){
//循環,外層依次求解 1....n的最優值
for (int j=;j<=n;j++){
int q=-;
//内層，依次在 1 .. j 中求出最大值，
//例如
// 當 j =1 的時候，q=max(q,p[1]+r[0]) .求的r[1]的最優值
// 當 j =2 的時候，q=max(q,p[1]+r[1])，然後再是 q=max(q,p[2]+r[0]) ，求的r[2]的最優值
// ... 以此類推
for (int i=;i<=j;i++){
if (q<p[i]+r[j-i]){
q=p[i]+r[j-i];
//記錄長度為 j 的鋼條 第一下開始切割的位置 i .
s[j]=i;
}
}
//記錄 j 的最優值
r[j]=q;
}
}
/**
* 輸出最優值和切割方案的函數
* @param p 價格表
* @param n 鋼條長度
*/
public void print_cut_rod_solution(int[] p,int n){
//一個數組，用r[i] 來儲存 鋼條長度為 i 的時候的最優值，初始值賦為 0.
int[] r= new int[n+];
for (int i=;i<r.length;i++){
r[i]=;
}
int[] s = new int[n+];
for (int i=;i<r.length;i++){
s[i]=;
}
//調用求最優值和方案的函數
extended_button_up_cut_rod(p,n,r,s);
System.out.print("n="+n+" 的最優值為："+r[n]+" , 切割方案為：");
//當 n>0 的時候，表明還有長度需要切割，哪怕做0切割
while (n>){
//輸出，組合方案
System.out.print(s[n] + "+");
//改變 n 的值，n=s[n]表示 已經切割下了s[n]那麼長，剩下的要怎麼切割
n=n-s[n];
}
}
1.4.1 程式結果：
可以參考上面給出的表格中的資料
1.4總結：
第一種直接的自頂向下的遞歸方法，沒有考慮子問題重疊問題，時間複雜度為指數級問題規模稍微大一點，比如（n=30）,時間複雜度就不能忍受了。
第二種自上而下的帶備忘錄遞歸方法，考慮了子問題重疊問題，利用空間來儲存求得的結果，時間複雜度為o(n^2)，效果較好。
第三種自下而上的方法，很自然的考慮了子問題重疊問題，時間複雜度為o(n^2)，沒有頻繁的遞歸調用的開銷，這種方法具有更下的系數。更好。和第二種方法空間複雜度一樣都是O(n)