#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