java，动态规划，算法导论之钢条切割（O（n）时间渐进性）

动态规划总结：

动态规划用于处理具有最优子结构，子问题重叠且互不相关的情况。由于子问题有所重叠，故此，为节省运行时间，每个子问题只求一次，通过“自顶向下带备忘录法”或“自底向上迭代法”来记录和应用已求得结果的子问题。能把递归结构次数从指数次降低到多项数次，使问题能快速求解。

动态规划和分治法把大问题化成小问题思想有点类似，却又有不同，分治法的子问题没有重叠。

思想步骤：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)));	}}