很容易看出来这是一个DP问题，跟之前的求数组中最长递增子序列是类似的。状态转移方程就是LIS[i]=max{1,LIS[k]+1} (a[i]和a[k]是兼容的for any k i)。而且更重要的是我们还可以根据结束时间给每一个活动排序，这样代码就更容易写出来，这里就不贴了。
如果是这个DP方程的话，我们是没法从DP过渡到贪心的。我们再来看一个更好的DP算法。既然是DP，肯定要找状态转移方程。不过我们先来寻找子问题，什么是这个原问题的子问题呢？我们刚才说到，活动选择问题就是要选择一个由兼容活动构成的最大集合。子问题是什么，兼容活动集合，这样的子问题有2^n。所以我们才用DP来优化它，如果子问题的最优解可以构造成原问题的最优解，那么此问题就具有最优子结构。定义S[i,j]={a[k]∈S:f[i] =s[k] f[k] =s[j]}(S是所有活动集合)。S[i,j]就是原问题集合S的子问题，其中的每个活动都是在活动a[i]结束之后开始，且在a[j]开始之前结束。更重要的是S[i,j]中的活动都要相互兼容。为了表示完整的问题结合，虚构两个活动a[0],a[n+1],f[0]=0,s[n+1]=∞。这样S=S[0，n+1]。
为了减少问题的处理量，给所以的活动按结束时间递增的顺序排序。这样的话如果i =j,S[i,j]=∅。为啥呢？因为这是不可能的，假设有一个a[k]∈S[i,j],则f[i] =sk fk =sj。说明a[i]活动排在a[j]活动前面，也即是i j。这与i =j矛盾。所以来说，如果将活动按结束时间非递减排序的话，则子问题就是S[i,j]，0 =i j =n+1,其他的S[i,j]是空集。针对于S[i,j]中的a[k]，我们把子问题分成S[i,k],S[k,j]和a[k]。则S[i,j]的最优解就是S[i,k]的最优解加上S[k,j]的最优解捎带一个a[k]的并集。证明子问题的最优解能构造原问题的方法就是剪贴法，不多说了。这样状态转移方程就有了，设C[i,j]是S[i,j]的最优解，即是S[i,j]中最大兼容活动数。当S[i,j]=∅(i =j)，此时C[i,j]=0。则状态转移方程就是C[i,j]=C[i,k]+C[k,j]+1虽然有了状态转移方程，但是对于每一个子问题都有k个选择，k=j-i-1(j-i+1-2),k=i+1….j-1。所以状态方程变了状态转移方程有了，这样很容易写出代码来，自底向上。
可是我们发现一个问题，那就是对于任何一个k将S[i,j]划分成两个子问题。可是如果有一个子问题是空的，那不是减少了我们的工作量吗？定理:对于任何非空S[i,j]，设a[m]是S[i,j]中最早结束的一个活动，f[m]=min{f[k]:a[k]∈S[i,j]}，则 1 活动a[m]被包含在S[i,j]的一个（可能有多个）最大兼容活动的子集中； 2 子问题S[i,m]是空集，a[m]使S[m,j]成为仅有的非空子问题。
简要证明一下：对于1，假设a[k]是S[i,j]最优解C[i,j]的第一个活动（排序之后），如果a[m]=a[k],结论得证.如果a[m],a[k]不相等，那么就用a[m]替换a[k]（因为a[m]是最早结束的活动，替换之后肯定和其他的兼容），原问题的最大兼容活动数目没变，结论得证。对于2，很简单，一看就明白了。这个定理给我们带来了什么好处呢？好处就是两个子问题其中一个为空了，减少工作量了。还有就是最早结束的活动肯定就是当前子问题的最优活动！在之前的DP，我们每次要做j-i-1次选择，而现在我们只需要选择当前最早结束的活动即可。而且你选择了a[m]，那么剩余问题的最优解就是S[m,j]的最优解。这样状态转移方程就是C[i,j]=C[m,j]+1(a[m]是S[i,j]中最早结束的活动，而且a[m]与最优解中之前的活动是兼容的，因为最早结束的 活动是当前子问题的一个最优活动，但是如果跟之前的已经找到的最优活动不兼容的话就没什么意义了吧)。这样还有一个好处就是代码不用在自底向上了，直接采用自顶向下来做就好了。我们找到了a[m]，直接找S[m,j]的最优解就好了。这就是贪心算法，每次都选择当前最好的选择。对于原问题来说，a[1]肯定是原问题S[0，n+1]最优解的第一个，而a[2]就不一定是S[1,n+1]的最优解的一个，因为a[2]不一定与a[1]兼容。意思就是已经选定是最优活动，那么之后选择的最优要和之前选定的活动兼容。这样每次选择的活动都是和之前兼容，那所有的活动也就是只是考虑一次而已。
伪代码，每次选择的a[m]都要和a[i]兼容,而且是第一个和a[i]兼容的。
