电路布线的问题提出是，在一块电路板的上、下两端分别有n个接线柱，用导线
将上端接线柱与下端接线柱相连，其中
是
的一个排列。要求将这n条导线分布到若干绝缘层上，当且仅当两条导线之间无交叉才可以设在同一层。电路布线问题要求确定一个能够布设在同一层的导线集
的最大不相交子集。设
。
1）写出电路布线问题最优值递归定义。
0, j < π(1)
当i=1时，size(1,j)={
1, j > =π(1)

当i>1时， size(i-1,j),j<π(i) , j <π(i)
Size(I,j)={
Max{size(i-1,j),size(i-1,π(i-1)+1}，j>=π(i)

package nine;

public class today {
//	static int[] c = {6,8,12,2,1,4,5,3,11,7,10,9,13};
	static int[] c = {8,7,4,2,5,1,9,3,10,6};
	static int n = c.length;
	static int[][] size = new int[n+1][n+1];
	static int[] net = new int[n];
	
	public static void main(String[] args) {
		mnset(c , size);//计算最优值
		int result = traceback(c , size , net);//计算最优解
		System.out.println("c:");
		show(c);
		System.out.println("size:");
		show(size);
		System.out.println("net（the optimal solution）:");
		show(net);
		System.out.println("the optimal value is "+result);
	}
	
	public static void mnset(int[] c , int[][] size){
		for(int j = 0;j < c[0];j++)
			size[0][j] = 0;//在第一个上接线柱之前都没有线可以连，对应size表的第一行为0的部分
		for(int j = c[0];j <= n;j++)
			size[0][j] = 1;//在第一个上接线柱接线以后，也只有一条线（每个接线柱只能连接一条线）
		for(int i = 1;i < n;i++)//依次加入第二个。。第三个。。至第n个接线柱
		{
			for(int j = 0;j < c[i];j++)//在当前这个接线柱接线之前都没有线可以连，故其值与上方相同，也是为0
				size[i][j] = size[i-1][j];
			for(int j = c[i];j <= n;j++)//当有线可以连的时候，要做出决定，将其加入到最大不相交子集中或者不加入（两个都计算，取最优值，即更大的size）
				size[i][j] = Math.max(size[i-1][j], size[i-1][c[i]-1]+1);//前提是不相交，并且最优值做出决定后值更好（大）
		}
		size[n][n] = Math.max(size[n-1][n], size[n-1][c[n-1]-1]+1);
	}
	
	public static int traceback(int[] c , int[][] size , int[] net){//回溯，显示最优解
		int j = n;
		int m = 0;
		for(int i = n;i > 1;i--)//10
			if(size[i][j] != size[i-1][j])//size[10][10]!=size[9][10]，比较表中上下两个值是否相等
			{
				net[m++] = i+1;//记录变化后的接线柱
				j = c[i]-1;//接下来查询的范围界限
			}
		if(j >= c[0])//若最后划分的区域（不相交区域）中有1号接线柱，则将其加入
			net[m++] = 1;
		return m;
	}
	
	public static void show(int[] a)
	{
		for(int i:a)
		{
			if(i == 0) break;
			System.out.print(i+" ");
		}
		System.out.println();
	}
	
	public static void show(int[][] a)
	{
		for(int i = 0;i < a.length - 1;++i)
		{
			for(int j = 0;j < a[i].length;++j)
			{
				System.out.print(a[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
}

运行结果截图：

3）分析算法的时间复杂性。
由代码可得，有两个for循环嵌套，故T(n) = O(n²)
来自课本《算法基础与实验》