Activity Selector DPアルゴリズム

#include <stdio.h>

#define MAX 1000
#define NUM 13
int DP_ActivitySelector(int i, int j, int s[], int f[], int A[][NUM])
{
	int k;
    int temp=0;
	int max=0;
	if(A[i][j] != -1) return A[i][j];

	if(i == j)    return max;
	else 
	{
		for(k = i+1; k < j; k++)
		{
			if(s[k] < f[i] || f[k] >s[j] ) return max;
			else
			{
				temp = DP_ActivitySelector(i, k, s, f, A) + DP_ActivitySelector(k, j, s, f, A) +1 ;

				if(temp > max) 
					max=temp;
				temp=0;
			}
		}
		A[i][j] = max;
		return max;		
	}
}

int main()
{
	int s[] = {0,1, 3, 0, 5, 3 ,5, 6, 8 ,8 ,2 ,MAX};

	int f[] = {0,4, 5 ,6 ,7, 8, 9, 10, 11, 12, 13,MAX};
	int A[NUM][NUM];

	for(int i=0; i<NUM; i++)
		for(int j=0; j<NUM; j++)
	{
		A[i][j]=-1;
	}
	printf("%d
", DP_ActivitySelector(0, 11, s, f, A));
}