COINS SOLUTION

coins.cpp

//https://algospot.com/judge/problem/read/COINS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

#define MAX_COINS 100
#define MAX_EXCHANGE 5000
#define OVER_CASE 1000000007

using namespace std;

vector<int> coins;
int cache[MAX_EXCHANGE][MAX_COINS];

int getExchangeCount(int money, int coinIndex) {
  int& ret = cache[money][coinIndex];
  if (ret != -1) {
    return ret;
  }

  if (money == 0) {
    return ret = 1;
  }

  if (coinIndex == 0) {
    if (money % coins[coinIndex] == 0) {
      return ret = 1;
    }

    return ret = 0;
  }

  ret = 0;
  int sum = 0;
  for (sum = 0; sum <= money; sum += coins[coinIndex]) {
    ret = (ret + getExchangeCount(money - sum, coinIndex - 1)) % OVER_CASE;
  }

  return ret;
}

int main() {
  int T;
  scanf("%d\n", &T);

  while (T-- > 0) {
    int M, C;
    scanf("%d %d", &M, &C);

    coins.clear();
    for (int i = 0; i < C; i++) {
      int coin;
      scanf("%d", &coin);
      coins.push_back(coin);
    }
    sort(coins.begin(), coins.end());

    memset(cache, -1, sizeof(cache));
    printf("%d\n", getExchangeCount(M, C - 1));
  }

  return 0;
}