一个递归解

　　设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<
         
        
       
      

运行结果：