Question

Using Java programming languague find the total number of different coin changes to make change for N cents, and we have infinite supply of each of S = {5, 2, 1} valued coins.

Answer 1

import java.util.Arrays;

class CoinChange

{

    static long countWays(int S[], int m, int n)

    {

        long[] table = new long[n+1];

        Arrays.fill(table, 0);   //O(n)

        table[0] = 1;

        for (int i=0; i<m; i++)

            for (int j=S[i]; j<=n; j++)

                table[j] += table[j-S[i]];

return table[n];

    }

public static void main(String args[])

    {

        int arr[] = {5,2,1};

        int m = arr.length;

        int n = 4;

        System.out.println(countWays(arr, m, n));

    }

}