原文: 算法起步之动态规划

       动态规划其实是类似于分治算法，说白就是要解决这类问题需要依赖一个个的子问题解决。动态规划通常是用来求解最优化问题，设计一个动态规划的算法一般需要四步：

• 刻画一个最优解的结构特征。
• 递归定义最优解的值。
• 计算最优解的值采用自底向上的方法。
• 利用计算出的信息构造一个最优解。

      但是一般我们只需要前三步即可，第4步是根据最优值来求最优解的构成。

      我们先通过一个具体的例子来了解一下。

      下图是某公司出售的一段长度为i英寸的共条的价格表：

长度i	1	2	3	4	5	6	7	8	9	10
价格p	1	5	8	9	10	17	17	20	24	30

       求切割方案，使得销售收益最大，假设切割是零成本。大家可以注意到n=4时不切割价格是9而切割成2个2英寸的钢条价格则变成了10；显然这种切割方案可以获得最大利润，但是如果数值比较大那我们改怎么计算呢，假设我们的钢条长度为g，我们可以将其分为2份，gi+gr；gi与gr的利润最大值加起来则是g的最大利润，我们使gi在1到10之间取值，显然gi的值我们可以先求出，而求gr的最大利润问题跟我们原问题又相同，很明显我们可以通过递归来解决这个问题。递归的方法：

public void start(int l){
		int[] p=null;
		if(l>=10){
			p=new int[l+1];
		}else{
			p=new int[11];
		}
		p[1]=1;
		p[2]=5;
		p[3]=8;
		p[4]=9;
		p[5]=10;
		p[6]=17;
		p[7]=17;
		p[8]=20;
		p[9]=24;
		p[10]=30;
		int result=cutrow(p, l);
		System.out.println(result);
	}
	
	public int cutrow(int[] p,int n){
		if (n==0) {
			return 0;
		}
		int q=-1;
		for (int i = 1; i <=n; i++) {
			q=max(q, p[i]+cutrow(p,n-i));
		}
		return q;
	}
	
	public int max(int a,int b){
		if (a>b) {
			return a;
		}else {
			return b;
		}
		
	}

         这种方法可以解决问题，但是当数值变大后会发现运行效率不高。原因在于已经求得的最大值我们没有直接用，而又进行了递归运算，这里有两种解决方案，1带备忘的自顶向下方法2自底向上方法。

      带备忘的自顶向下方法：

public void start2(int l){
		int[] p=null;
		if(l>=10){
			p=new int[l+1];
		}else{
			p=new int[11];
		}
		p[1]=1;
		p[2]=5;
		p[3]=8;
		p[4]=9;
		p[5]=10;
		p[6]=17;
		p[7]=17;
		p[8]=20;
		p[9]=24;
		p[10]=30;
		int result=memoizedcutrod(p, l);
		System.out.println(result);
	}
	public int  memoizedcutrod(int[] p,int n){
		int[] r=new int[n+1];
		return memoizedcutronaux(p, n, r);
	}
	public int memoizedcutronaux(int[]p,int n,int[]r){
		if(r[n]>0){
			return r[n];
		}
		if(n==0){
			return 0;
		}else {
			int q=-1;
			for (int i = 1; i <= n; i++) {
				q=max(q, p[i]+memoizedcutronaux(p, n-i, r));
			}
			r[n]=q;
			return q;
		}
	}

      自底向上方法：

public void start1(int l){
		int[] p=null;
		if(l>=10){
			p=new int[l+1];
		}else{
			p=new int[11];
		}
		p[1]=1;
		p[2]=5;
		p[3]=8;
		p[4]=9;
		p[5]=10;
		p[6]=17;
		p[7]=17;
		p[8]=20;
		p[9]=24;
		p[10]=30;
		int result=buttomupcutrow(p, l);
		System.out.println(result);
	}
	
	
	public int buttomupcutrow(int[]p,int n){
		
		for(int j=1;j<=n;j++){
			int q=-1;
			for (int i = 1; i <=j; i++) {
				q=max(q,p[i]+p[j-i]);
			}
			p[j]=q;
		}
		return p[n];
		
	}

        可以看出自底向上的方法最为简单，这也是我们以后最为常用的一种方法。

         友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】