動態規劃總結：

動態規劃用于處理具有最優子結構，子問題重疊且互不相關的情況。由于子問題有所重疊，故此，為節省運行時間，每個子問題只求一次，通過“自頂向下帶備忘錄法”或“自底向上迭代法”來記錄和應用已求得結果的子問題。能把遞歸結構次數從指數次降低到多項數次，使問題能快速求解。

動態規劃和分治法把大問題化成小問題思想有點類似，卻又有不同，分治法的子問題沒有重疊。

思想步驟：1、分析最優子結構

2、遞歸定義最優解

3、求出最優解的值并記錄信息

4、構造出最優解具體方案

鋼條切割分析（漸進性可為O（n））：

以自底向上為例，算法導論上偽代碼如下

BOTTOM-UP-CUT-ROD(p, n)

let r[0..n] be a new array

r[0] = 0

for j = 1 to n

    q = -∞

    for i = 1 to j

        q = max(q, p[i] + r[j - i])

    r[j] = q

return r[n]

其中，p是已知價格的鋼條長度對應的價格，顯然，p的長度是固定的了，為一個常數，而n可為任意大，則偽代碼中第五和第六行（偽代碼加粗部分）中，i迭代到j，而j可迭代到n，則當n大于p的長度時，第六行將發生數組溢出錯誤,實際上,第六行不應該迭代到j，而是迭代到

Math.min(j, p.length)即可。

則代碼兩層循環中，第一次O（n）次，第二次O（p.length)次即可。所以，總的迭代次數O（n）次，故時間漸進性為O（n）。

因為java面向對象的特性，故此，在代碼中我增添了一點功能，可能會有點感覺污染了本文的標題，不過，以上分析只是我個人見解，不對之處還請指正。

代碼實現：

package dynamicPRogramming;import java.util.Arrays;// r, s, p中的index對應相應的長度，size對應最大長度public class BottomUpCutRod {	private int size = 0; // 已計算最優解的最大長度	private int capacity = 0; // r，s實際數組長度，初始化為最大長度的兩倍	private int[] r; // 存儲最優解的價格	private int[] s; // 存儲最優解的切割方案	private int[] p; // 價格表	// 設置價格表，并進一步最優實現方案初始化	public void setPrice(int[] p, int n) {		if (p.equals(this.p)) // 價格表沒有變化，直接返回			return;		this.p = Arrays.copyOfRange(p, 0, p.length);		this.size = n;		this.capacity = n * 2;		r = new int[capacity];		s = new int[capacity];		r[0] = 0;		initialProject(1, n);	}	// 返回長度為len時，可獲得的最優總價格	public int getBest(int len) {		if (len > capacity - 1) {			capacity = 2 * capacity; // 容量擴大兩倍			r = Arrays.copyOfRange(r, 0, capacity);			s = Arrays.copyOfRange(s, 0, capacity);		}		if (len > size) {			initialProject(size + 1, len);			size = len;		}		return r[len];	}	// 返回長度為n時的最優切割方案	public int[] getBestCut(int len) {		getBest(len);		StringBuilder sb = new StringBuilder();		while(s[len] != len) {			sb.append(s[len] + " ");			len = len - s[len];		}		sb.append(len);		String[] ss = sb.toString().split(" ");		int[] result = new int[ss.length];		for(int i = 0; i < ss.length; i++)			result[i] = Integer.parseInt(ss[i]);		return result;		}		// 輸出價格表及從1到size長度的對應最優價格和切割方案	public void printResult() {		System.out.print("        長度：");		for(int i = 1; i <= size; i++)			System.out.format("%-6d", i);		System.out.println();		System.out.print("        價格：");		for(int i = 1; i < p.length; i++)			System.out.format("%-6d", p[i]);		System.out.println();		System.out.print("最優價格：");		for(int i = 1; i <= size; i++)			System.out.format("%-6d", r[i]);		System.out.println();		System.out.print("最優切割：");		for(int i = 1; i <= size; i++)			System.out.format("%-6d", s[i]);	}		// 初始化從from到end長度的鋼條最優解	private void initialProject(int from, int end) {		for (int j = from; j <= end; j++) {			r[j] = -1;			for (int i = 1; i <= Math.min(j, p.length - 1); i++) {				int q = p[i] + r[j - i];				if (q > r[j]) {					r[j] = q;					s[j] = i;				}			}		}	}}
測試代碼：
package dynamicProgramming;import java.util.Arrays;public class TestBottomUpCutRod {	public static void main(String[] args) {		int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };		BottomUpCutRod b = new BottomUpCutRod();		b.setPrice(p, 10);		b.printResult();		System.out.println();		System.out.println("長度為18最優解： " + b.getBest(18) + "   切割方案: " + Arrays.toString(b.getBestCut(18)));	}}