// assignment: use memoization result to print out results for 
// ways to combine N matrices
//
#include <stdio.h>

int nk_array[32][16];
int insertion_count;
int number_recursive_calls;

// zero out array for memoization
void initialize (int n, int k) {
	int i = 1;
	int j;
	insertion_count = 0;
	// initially populate array
	nk_array[0][0] = 0; // blank value to simplify array accesses
	 while (i <= n) { // do first array
		  nk_array[i][0] = 1;
		  j = 1;
		  while (j <= k)  { 
			   if (j == i) nk_array[i][j++] = 1;
			   else nk_array[i][j++] = 0; // do second array
		  }
		  i++;
	 }
}


// memoized computing of the binomial coefficient
int memoized_bi(int n, int k) {
	if (nk_array[n-1][k-1] > 0) {
		 if (nk_array[n-1][k] > 0) {
			  // we have everything we need!
		 } else { // we don't have nk_array[n-1][k] yet
			   nk_array[n-1][k] = (int) memoized_bi(n-1,k);
			   insertion_count++;
		 }
	} else {   // we don't have nk_array[n-1][k-1] yet
		 nk_array[n-1][k-1] =  (int) memoized_bi(n-1, k-1);
		  nk_array[n-1][k] = (int) memoized_bi(n-1,k); // if we dont have nk_array[a][4] we can't have nk_array[a][5] either
		  insertion_count +=2;
	}
	return nk_array[n-1][k-1] + nk_array[n-1][k];
}

// do memoized_bi counting number_insertions
int do_memoized_bi(int x_value, int(*func)(int n,int k)) {
	int value;
	float float_value;
	int n = 2 * x_value;
	int k = x_value;
	 initialize(n,k);
	 value = (*func)(n,k);
  	float_value = (1.0/(x_value+1.0)) * value;
	printf("for %6d matrices, there are %.0f ways to combine them\n", x_value + 1,float_value);
}


// compute results for N == 11 and 16

int main(void){ 
	 printf("-----------------------------------------------------\n");
	 do_memoized_bi(10,memoized_bi);
	 do_memoized_bi(15,memoized_bi);
	 printf("\n");
	 printf("(note: used memoization for the binomial coefficients)\n");
	 printf("\n");
	 return(0);
}