UVa 357 - Let Me Count The Ways

## Codes

### Wrong way to solve the problem

357-LetMeCountTheWays_wrong.cpp

#include <iostream>
#include <stdint.h>

#define CANT_COINS 5

using namespace std;

uint64_t coins[CANT_COINS] = {1, 5, 10, 25, 50};

uint64_t ways(int32_t n, uint32_t max_coin) {
uint64_t result = 0;
uint32_t i = 0;
if (n < 0)
return 0;
if (n <= 1)
return 1;
for (; i < max_coin; ++i)
result += ways(n - coins[i], i+1);

return result;
}

int main() {

int32_t n;

while (cin >> n) {
uint64_t res = ways(n, CANT_COINS);
if (res == 1)
cout << "There is only 1 way to produce " << n << " cents change.\n";
else
cout << "There are " << res << " ways to produce " << n << " cents change.\n";
}
return 0;
}

### Right way to solve the problem

357-LetMeCountTheWays_right.cpp

#include <iostream>
#include <stdint.h>

#define CANT_COINS 5
#define MAX_CENTS 30001

using namespace std;

uint64_t coins[CANT_COINS] = {50, 25, 10, 5, 1};
uint64_t results[MAX_CENTS] = {0};

void init() {
uint32_t i, j, c;

results[0] = 1;

for(i = 0; i < CANT_COINS; ++i) {
c = coins[i];
for (j = c; j < MAX_CENTS; ++j)
results[j] += results[j-c];
}

}

int main() {
int32_t n;

init();

while (cin >> n) {
uint64_t res = results[n];
if (res == 1)
cout << "There is only 1 way to produce " << n << " cents change.\n";
else
cout << "There are " << res << " ways to produce " << n << " cents change.\n";
}
return 0;

}