Change a coin with one,two,five coins (print all ways), C++ (gcc)

Change a coin with one,two,five coins (print all ways)

//Title of this code

#include <iostream>

using namespace std;

//#############################################################

// need a helper because N0 = 1 which is wrong
int coinChangeHelper(int n) {
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;
    
    return coinChangeHelper(n - 1) + coinChangeHelper(n - 2) + coinChangeHelper(n - 5); 
}

int coinChange(int n) {
    if (n <= 0)
        return 0;

return coinChangeHelper(n);
}

//#############################################################

// dynamic programming
int coinChangeBetter(int n) {
    if (n <= 0)
        return 0;
    
    int t[n + 1];
    
    t[0] = 1;
    t[1] = 1;
    t[2] = 2;
    
    for (int i = 3; i <= n; ++i)
        t[i] = t[i - 1] + t[i - 2] + ((i - 5 >= 0) ? t[i - 5] : 0);

return t[n];
}

//#############################################################

// dynamic programming with O(1) space
int coinChangeBest(int n) {
    if (n <= 0)
        return 0;
    
    int t[6];
    
    t[0] = 1;  
    t[1] = 1;  
    t[2] = 2;  
    t[3] = 3;  
    t[4] = 5;

if (n > 0 && n < 5)
        return t[n];
  
    int i = 5;
    while (i <= n) {
    
        t[5] = t[5 - 1] + t[5 - 2] + t[5 - 5];

t[0] = t[1];
        t[1] = t[2];
        t[2] = t[3];
        t[3] = t[4];
        t[4] = t[5];
        
        ++i; 
    }

return t[5];
}

//#############################################################

int main()
{
    
    for (int i = -2; i < 15; ++i)
        cout << coinChange(i) << " ";
    
    cout << endl;
    
    for (int i = -2; i < 15; ++i)
        cout << coinChangeBetter(i) << " ";
    
    cout << endl;
    
    for (int i = -2; i < 15; ++i)
        cout << coinChangeBest(i) << " ";
        
    
   
    
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development