作電路板時艇拍，將n條連線分布到若干絕緣層上私爷。在同一層的連線不相交。電路布線問題就是要確定將哪些連線安排到第一層上斗躏，使該層上有盡可能多的連線逝慧。
用動態(tài)規(guī)劃和遞歸分別實現(xiàn)
動態(tài)規(guī)劃實現(xiàn)：
1、二維數(shù)組代表什么啄糙？size[i,j]意思是**上接線柱i與下接線柱j之間笛臣，最大可以放幾條線 **
2、數(shù)組打底：
3隧饼、遞推式：
//動態(tài)規(guī)劃解決
#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; //打好數(shù)組的底子
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;
}
遞歸實現(xiàn)：
//遞歸解法
#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;
}
運行截圖
