一个递归解

　　设c[i][j]为S_ij中最大兼容子集中的活动数目，当S_ij为空集时，c[i][j]=0；当S_ij非空时，若a_k在S_ij的最大兼容子集中被使用，则则问题S_ik和S_kj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。

当i≥j时，S_ij必定为空集，否则S_ij则需要根据上面提供的公式进行计算，如果找到一个a_k，则S_ij非空（此时满足f_i≤s_k且f_k≤s_j），找不到这样的a_k，则S_ij为空集。

c[i][j]的完整计算公式如下所示：

 

最优解计算过程

　　根据递归公式，采用自底向下的策略进行计算c[i][j]，程序实现如下所示：

#include 
     
      using namespace std;const int N = 11;int s[N+2]= {-1,1,3,0,5,3,5,6,8,8,2,12,65535};int f[N+2]= {-1,4,5,6,7,8,9,10,11,12,13,14,65535};//trace[i][j]跟踪子问题S(i,j)每次最优时的划分int trace[N+2][N+2];//dp[i][j]表示子问题S(i,j)的最多兼容活动数int dp[N+2][N+2];/*S(i,j)={ak,fi<=sk
      
       <=sj}表示在活动ai结束之后，在aj开始之前的活动集，则整个问题空间可表示为S(0,n+1),*其中添加活动a0和an+1，s0=f0=0,sn+1=fn+1=2^32-1*根据dp[i][j]的含义,假设S(i,j)中不包含任何的活动序列(即满足S(i,j)定义的活动不存在)，则dp[i][j]=0；*否则，假设ak时S(i,j)中存在的一个兼容活动,那*么这里存在问题S(i,j)的最优子结构:S(i,k)和S(k,j).*根据上面叙述，可以定义问题的递归解结构:*dp[i][j]=0,如果S(i,j) =NULL*dp[i][j]=max{dp[i][k]+dp[k][j]+1},i
       
        
          dp[i][j])                        {                            dp[i][j] = dp[i][k]+dp[k][j] +1;                            trace[i][j] = k;                        }                    }                }            }        }}void print(int i,int j){    int k =0;    if(trace[i][j]==0)        return;    k = trace[i][j];    cout << k << "  ";    print(i,k);    print(k,j);}int main(){    dp_solve();    print(0,N+1);    cout<
        
       
      
     

运行结果：