电路布线问题

作电路板时，将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;
}