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

int* initArr(int noOfElements) {
  int* arr = (int *)malloc(sizeof(int) * noOfElements);
  memset(arr, 0, noOfElements);
  return arr;
}

int numOfCalls = 0;
int change(int* coins, int noOfCoins, int amount) {
  numOfCalls++;

  static int* minChange = initArr(amount+1);

  if (minChange[amount] != 0) {
    //Number of coins for the searched amount had allreday been calculated.
    return minChange[amount];
  }

  for (int i=0; i<noOfCoins; i++) {
    if (amount == coins[i]) {
      //There was a coin of the searched amount.
      minChange[amount] = 1;
    }
  }

  if (minChange[amount] == 0) {
    int minCoins = INT_MAX;
    int n;
    for (int i=1; i<=amount/2; i++) {
      n = change(coins, noOfCoins, amount-i) + change(coins, noOfCoins, i);
      if (n < minCoins) {
	minCoins = n;
      }
    }
    minChange[amount] = minCoins;
  }

  return minChange[amount];

}

main(int argn, char** args) {
  int coins[] = {1, 5, 10, 20, 50, 100, 500, 1000};
  int noOfCoins = 8;

  printf("Det krävs %d mynt.\n", change(coins, noOfCoins, atoi(args[1])));
  printf("Det krävdes %d anrop\n", numOfCalls);
}