Consider a country having monetary coins of values (2,3,7). a. Using dynamic programming, write an algorithm that finds the number of ways to construct an amount N. b. What is the complexity of your algorithm? c. Show the dynamic programming table for an input of N=10. For N=10 the solution is 3: (2,2,2,2,2) (2,2,3,3) (3,7).

CoinOfValues.java

public class CoinOfValues {

    public static void main(String[] args) {
        int number = 10;
        int[] coins = {2, 3, 7};
        int[][] dpMatrix = new int[coins.length + 1][number + 1];
        for (int i = 0; i <= coins.length; i++)
            dpMatrix[i][0] = 1;
        for (int i = 1; i <= number; i++)
            dpMatrix[0][i] = 0;
        for (int i = 1; i <= coins.length; i++)
            for (int j = 1; j <= number; j++)
                if (coins[i - 1] <= j)
                    dpMatrix[i][j] = dpMatrix[i - 1][j] + dpMatrix[i][j - coins[i - 1]];
                else
                    dpMatrix[i][j] = dpMatrix[i - 1][j];
        for (int i = 0; i <= coins.length; i++)
            for (int j = 0; j <= number; j++)
                System.out.print(((j==0)?"\n":" ")+dpMatrix[i][j] );

        System.out.println("\nresult: "+dpMatrix[coins.length][number]);
    }

}

|SampleOutput.txt

1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0 1
1 0 1 1 1 1 2 1 2 2 2
1 0 1 1 1 1 2 2 2 3 3
result: 3