... This is a DP problem that can be computed recursively the only thing you should take care of is integer overflows so you can use c++ long long or java long or BigInteger class.
Here is wahab1 java solution using java BigInteger class
/*
ID: wahab1
PROG: money
LANG: JAVA
*/
import java.math.*;
import java.io.*;
import java.util.*;
public class money
{
static int coins[]=new int[25];
static BigInteger val[][]=new BigInteger[25][10001];
public static BigInteger compute(int v,int k)
{
if(k==0)
return v%coins[k]==0?BigInteger.ONE:BigInteger.ZERO;
if(v==0)
return BigInteger.ONE;
if(v<0)
return BigInteger.ZERO;
if(val[k][v]!=null)
return val[k][v];
return val[k][v]=compute(v,k-1).add(compute(v-coins[k],k));
}
public static void main(String[] args) throws Exception
{
FileReader in=new FileReader("money.in");
PrintWriter out=new PrintWriter(new FileWriter("money.out"));
StreamTokenizer st=new StreamTokenizer(in);
int n,v;
st.nextToken();
n=(int)st.nval;
st.nextToken();
v=(int)st.nval;
for(int i=0;i<n;i++)
{
st.nextToken();
coins[i]=(int)st.nval;
}
out.println(compute(v,n-1));
out.close();
}
}
Это цитата из анализа задачи USACO 2007 October Gold: Problem 1. Cow Cash