memoization.c

#include <stdio.h>
#include <stdlib.h>

int max(int x, int y) {
  if(x > y) return x;
  return y;
}

int func_aux(int N, int sols[]) {
  if(N <= 1) return 1;
  if(sols[N] != -1) return sols[N];
  
  printf("Calculating %d...\n", N);
  int res = func_aux(N-1, sols);
  sols[N] = res;

  return res;
}

int func(int N) {
  int x, y;
  int sols[N+1];
  
  for(x = 0; x < N+1; x++) sols[x] = -1;
  x = func_aux(N-1, sols);
  y = func_aux(N-2, sols);

  return max(2*y, 3+x);
}

int main() {
  int i = func(10);
  printf("%d\n", i);
}