Coins Change

#!/usr/bin/python3

def DPGetChange(coinset, biggercoin) :

    num_coins = len (coinset)
    dptable = [0] * (num_coins+1)
    for r in range (num_coins+1) :
        dptable[r] = [0] * (biggercoin+1);

    # Coins of values(v) greater than 0 cannot be obtained with coins of value 0
    for v in range (1, biggercoin+1) :
        dptable[0][v] = 0;

    # Coin of value 0 can be obtained with any given coins(c) in 1 way
    for c in range (num_coins+1) :
        dptable[c][0] = 1;

    for c in range (1, num_coins+1) :
        for v in range (1, biggercoin+1) :
            if (v >= coinset[c-1]) :
                # Exclude last coin in the coinset + Include last coin in the coinset
                dptable[c][v] = dptable[c-1][v] + dptable[c][v-coinset[c-1]]
            else :
                dptable[c][v] = dptable[c-1][v] # Exclude last coin in the coinset

    return dptable[num_coins][biggercoin];

def GetChange(coinset, numcoins, biggercoin) :

    # Coin of value 0 can be obtained with any given values in 1 way
    if biggercoin == 0:
       return 1

    # With no available coins for change, we cannot obtain any value
    if numcoins == 0:
       return 0

    if biggercoin >= coinset[numcoins-1]:
              # Get change excluding the last coin in the coin set + Get change including the last coin in the coin set
       return GetChange(coinset, numcoins-1, biggercoin) + GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1])
    else:
       return GetChange(coinset, numcoins-1, biggercoin) # Get change excluding the last coin as it has a bigger value

biggercoin = 4;
coinset_1 = [ 1, 2, 3 ] # Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3)
print("Using dynamic programming:" + str ( DPGetChange(coinset_1, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_1, len(coinset_1), biggercoin) ) )

biggercoin = 6;
coinset_2 = [ 2, 3, 4 ] # Three ways : (2,2,2) (2,4) (3,3)
print("Using dynamic programming:" + str ( DPGetChange(coinset_2, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_2, len(coinset_2), biggercoin) ) )

biggercoin = 10;
coinset_3 = [ 2, 5, 8, 9, 10 ] # Four ways : (2,2,2,2,2) (2,8) (5,5) (10)
print("Using dynamic programming:" + str (DPGetChange (coinset_3, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_3, len(coinset_3), biggercoin) ) )

biggercoin = 10;
coinset_4 = [ 8, 9, 10 ] # 1 way : (10)
print("Using dynamic programming:" + str (DPGetChange(coinset_4, biggercoin) ) )
print("Using recursion:" + str ( GetChange(coinset_4, len(coinset_4), biggercoin) ) )

Using dynamic programming:4
Using recursion:4
Using dynamic programming:3
Using recursion:3
Using dynamic programming:4
Using recursion:4
Using dynamic programming:1
Using recursion:1

#include<iostream>
#include<vector>

using namespace std;

// DP solution for making coin change
int DPGetChange (vector<int>& coinset, int biggercoin) {

    int num_coins = coinset.size();
    int dptable[num_coins+1][biggercoin+1];

    // Coins of values greater than 0 cannot be obtained with coins of value 0
    for (int c=1; c<=biggercoin; c++) {
        dptable[0][c] = 0;
    }

    // Coin of value 0 can be obtained with any given coins in 1 way
    for (int r=0; r<=num_coins; r++) {
        dptable[r][0] = 1;
    }

    for (int r=1; r<=num_coins; r++) {
        for (int c=1; c<=biggercoin; c++) {
            if (c >= coinset[r-1]) {
                // Exclude last coin in the coinset + Include last coin in the coinset
                dptable[r][c] = dptable[r-1][c] + dptable[r][c-coinset[r-1]];
            } else {
                dptable[r][c] = dptable[r-1][c]; // Exclude last
            }
        }
    }

    return dptable[num_coins][biggercoin];
}

// Recursive solution for making coin change
int GetChange (vector<int>& coinset, int numcoins, int biggercoin) {

    // Coin of value 0 can be obtained with any given values in 1 way
    if (biggercoin == 0)
        return 1;

    // With no available coins for change, we cannot obtain any value
    if (numcoins == 0)
        return 0;

    if (biggercoin >= coinset[numcoins-1])
        return GetChange (coinset, numcoins-1, biggercoin) + // Get change excluding the last coin in the coin set
               GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1]); // Get change including the last coin in the coin set
    else
        return GetChange (coinset, numcoins-1, biggercoin); // Get change excluding the last coin
}

int main(){

    int coin1 = 4;
    vector<int> coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */

    int coin2 = 6;
    vector<int> coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */

    int coin3 = 10;
    vector<int> coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */

    cout << "Number of ways of making coin change using dynamic programming" << endl;
    cout << DPGetChange (coinset_1, coin1) << endl;
    cout << DPGetChange (coinset_2, coin2) << endl;
    cout << DPGetChange (coinset_3, coin3) << endl;

    cout << "Number of ways of making coin change using recursion" << endl;
    cout << GetChange (coinset_1, coinset_1.size(), coin1) << endl;
    cout << GetChange (coinset_2, coinset_2.size(), coin2) << endl;
    cout << GetChange (coinset_3, coinset_3.size(), coin3) << endl;

    return 0;
}

Number of ways of making coin change using dynamic programming
4
3
4
Number of ways of making coin change using recursion
4
3
4