Thursday, January 28, 2016

Coin change problem

#include <iostream>
using namespace std;

int count (int * a, int m , int amount) {

int s[amount+1][m];
int x, y;

for (int i = 0; i < m; i++) {
s[0][i] = 1;
}

for (int i = 1 ;i <= amount; i++) {
for (int j = 0; j < m ; j++) {
x = i - a[j] >= 0 ?  s[i-a[j]][j] : 0;
y = j-1 >= 0 ? s[i][j-1] : 0;

s[i][j] = x + y;
}
}

return s[amount][m-1];
}

int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int amount = 4;
    printf(" %d ", count(arr, m, amount));
    return 0;
}

No comments: