Coin Change Problem

 #include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// recursive

int count(vector<int> &coins, int m, int n) {

    if (n == 0) 

        return 1;

    if (n < 0)

        return 0;

     if (m <= 0 && n >= 1)

        return 0;

    return count(coins, m-1, n) + count(coins, m, n-coins[m-1]);

}

// recursive with memoization

unsigned long dp[51][251];// global array initialized to 0 

unsigned long countDP1(vector<int> & coins,  int i, int n)

{

    if(n == 0)

        return 1; //no coins

    if(n < 0) 

        return 0; //no negative money      

    if(i == coins.size()) //no more options of coins

        return 0;

    if(dp[i][n]!=0)

        return dp[i][n];

        //leave it or take it

    return dp[i][n] = countDP1(coins,i+1, n) + countDP1(coins,i, n-coins[i]);

}

//loop with 2D memoization space O(n*m) time O(n*m)

unsigned long countDP2(vector<int> &coins, int m, int n ) 

{ 

    int i, j; 

    unsigned long table[n + 1][m],  x, y; 

    for (i = 0; i < m; i++) 

          table[0][i] = 1;  

     for (i = 1; i < n + 1; i++) 

    { 

        for (j = 0; j < m; j++) 

        { 

            // Count of solutions including coins[j] 

            x = (i-coins[j] >= 0) ? table[i - coins[j]][j] : 0; 

            // Count of solutions excluding coins[j] 

            y = (j >= 1) ? table[i][j - 1] : 0; 

            // total count 

            table[i][j] = x + y; 

        } 

    } 

    return table[n][m - 1]; 

}

// loop with 1D memoization space O(n) time O(n*m)

unsigned long countDP( vector<int> &coins, int m, int n ) 

{ 

      unsigned long table[n + 1]; 

    memset(table, 0, sizeof(table)); 

      table[0] = 1; 

      for(int i=0; i< m; i++) 

        for(int j=coins[i]; j <= n; j++) 

            table[j] += table[j-coins[i]]; 

      return table[n]; 

} 

// Complete the ways function below.

unsigned long ways(int n, vector<int> coins) {

    return countDP(coins, coins.size(), n);

    //return countDP1(coins, 0, n);

}

int main()

{

    ofstream fout(getenv("OUTPUT_PATH"));

    string nm_temp;

    getline(cin, nm_temp);

    vector<string> nm = split_string(nm_temp);

    int n = stoi(nm[0]);

    int m = stoi(nm[1]);

    string coins_temp_temp;

    getline(cin, coins_temp_temp);

    vector<string> coins_temp = split_string(coins_temp_temp);

    vector<int> coins(m);

    for (int i = 0; i < m; i++) {

        int coins_item = stoi(coins_temp[i]);

        coins[i] = coins_item;

    }

    unsigned long res = ways(n, coins);

    fout << res << "\n";

    fout.close();

    return 0;

}

vector<string> split_string(string input_string) {

    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {

        return x == y and x == ' ';

    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {

        input_string.pop_back();

    }

    vector<string> splits;

    char delimiter = ' ';

    size_t i = 0;

    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {

        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;

        pos = input_string.find(delimiter, i);

    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;

}