作电路板时，将n条连线分布到若干绝缘层上。在同一层的连线不相交。电路布线问题就是要确定将哪些连线安排到第一层上，使该层上有尽可能多的连线。
用动态规划和递归分别实现
动态规划实现：
1、二维数组代表什么？size[i,j]意思是**上接线柱i与下接线柱j之间，最大可以放几条线 **
2、数组打底：
3、递推式：
//动态规划解决
#include<stdio.h>
#define n 10 //10个接线柱
int p[n]={7,6,3,1,4,0,8,2,9,5};//下标是上接线柱，值是该接线柱连的下接线柱
int size[n][n]; //上接线柱n与下接线柱n之间，最大可以放几条线
int main(){
int a=0,b=0;
for(int i=0;i<p[0];i++) //
size[0][i]=0; //打好数组的底子
for(int i=p[0];i<n;i++) //
size[0][i]=1; //
for(int i=1;i<n;i++){ //遍历上接线柱
for(int j=0;j<p[i];j++)
size[i][j]=size[i-1][j];
for(int j=p[i];j<n;j++){
a=1+size[i-1][p[i]-1];
b=size[i-1][j];
size[i][j]=a>b?a:b;
}
}
printf("%d\n",size[9][9]);
return 0;
}
递归实现：
//递归解法
#include<stdio.h>
#define n 10 //10个接线柱
int p[n]={7,6,3,1,4,0,8,2,9,5};
int Size(int i,int j){
if(i==0){
if(j<p[0])
return 0;
else
return 1;
}
if(j<p[i]){
return Size(i-1,j);
}
int a,b;
a=1+Size(i-1,p[i]-1);
b=Size(i-1,j);
return a>b?a:b;
}
int main(){
printf("%d\n",Size(9,9));//在此题中9,9就是最底层，所以从最底层开始
return 0;
}
运行截图
