Divide and conquer algorithm for making change with limited coins

Question

The algorithm is supposed to find the number of ways change can be made for an input amount using only dimes, nickels, and pennies. My approach was to use a divide and conquer strategy and split the problem by finding the number of ways change can be made with the biggest coin, a dime, and the number of ways to make change without using a dime. I have written an implementation for this algorithm that solves the problem correctly for inputs from 1...14 but when the input is equal to or larger than 15 the returned result is incorrect. Obviously my algorithm is wrong and was wondering what changes need to be made to fix the code and if my approach is a proper divide and conquer solution.

The code is as follows:

    public static int makeChange(int n) {

        if(n < 0)
            return 0;
        else  {

        int sum = makeChange(n-10) + makeChange(n-5) + 1;

        return sum;
     }
}

Many thanks.

Answer 1

Hint:

int nways_10 (int n) {
    int s = 0;
    int d = n / 10;

    for (int i = 0; i <= d; ++i) {
        s += nways_5 (n - 10*i);
    }

    return s;
}

You should get the idea how to write nways_5 and other functions, if needed.