Question 20

public class CoinCounting{
    public static void main (String[] args){
        CoinCounting c = new CoinCounting();
        int target = 5;
        int[] coinSizes = {1, 2, 5};
        System.out.println(c.coinCount(target, coinSizes));
    }

    private void generateWays(int coin, int target, int[] ways){
        for (int j = coin; j <= target; j++) {
            ways[j] += ways[j - coin];
        }
    }

    public int coinCount(int target, int[] coinSizes){
        int[] ways = new int[target+1];
        ways[0] = 1;

        for (int i = 0; i < coinSizes.length; i++) {
            generateWays(coinSizes[i], target, ways);
        }

        return ways[ways.length-1];
    }
}