#include<bits/stdc++.h>
using namespace std;
long long int getWays(vector<long long int>coins, long long int n, long long int m)
{
long long int dp[m][n+1], p;
for(int j=1;j<=n;j++)
{
if(j==coins[j]||(j%coins[0])==0)
dp[0][j] = 1;
else
dp[0][j] = 0;
}
for(int i=1;i<m;i++)
{
for(int j=1;j<=n;j++)
{
if(coins[i]>=j)
{
dp[i][j] = dp[i-1][j];
if(coins[i] == j)
dp[i][j]+= 1;
}
else
{
if(j>=(coins[i]*2))
{
dp[i][j] = dp[i-1][j]+dp[i][(j-coins[i])];
}
else {
dp[i][j] = dp[i-1][j]+dp[i-1][(j-coins[i])];
p = (j%coins[i])?0:1;
dp[i][j]+=p;
}
}
}
}
return dp[m-1][n];
}
int main()
{
long long int n,m,i;
scanf("%lld%lld",&n,&m);
vector<long long int>coins(m);
for(i=0;i<m;i++)
{
scanf("%lld",&coins[i]);
}
if(n==0)
cout<<0;
else {
cout<<getWays(coins, n, m);
}
return 0;
}
- Problem Description
How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.
Task
Write a program that, given
1.The amount N to make change for and the number of types M of infinitely available coins
2. A list of M coins – C={C1, C2, C3,…,CM}
Prints out how many different ways you can make change from the coins to STDOUT.
Input Format
First line will contain 2 integer N and M respectively.
Second line contain M integer that represent list of distinct coins that are available in infinite amount.
Constraints
1<=Ci<=50
1<=N<=250
1<=M<=50
The list of coins will contain distinct integers.
Output Format
One integer which is the number of ways in which we can get a sum of N from the given infinite supply of M types of coins. - Test Case 1
Input (stdin)4 3
1 2 3
Expected Output4 - Test Case 2
Input (stdin)10 4
2 5 3 6
Expected Output5