Imagine we are at a grocery store's checkout, and we pay in cash. The total price for our grocery is $73.23 and we give the cashier $75. The cashier needs to decide how to give us change. The total money value that they need to give us is $1.77 (or 177 cents). And the cashier has quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent.) The problem is to find the minimum number of coins as change.

Formally, there are two inputs:

1. faceValues: a positive integer array that denotes the face values of the available coins. The array does not have duplicate numbers.
2. money: a positive integer number that denotes the change

package main.java;

import java.util.HashMap;

public class DP_Exercise { /** * This method should be recursive. * The method should implement the algorithm we talked in the class. * * @param faceValues face values of coins. * @param money the target money. * @return the minimum number of coins that equal to money */ public static int recursiveChange(int[] faceValues, int money) { // please replace the following line with your implementation return -1; }

/** * This method should not have any recursive call and use memoization. * * * @param faceValues face values of coins. * @param money the target money. * @return the minimum number of coins that equal to money */ public static int memoChange(int[] faceValues, int money, HashMap memo) { // please replace the following line with your implementation return -1; }

/** * This method should not have any recursive call and use tabulation. * * * @param faceValues face values of coins. * @param money the target money. * @return the minimum number of coins that equal to money */ public static int tabChange(int[] faceValues, int money) { // please replace the following line with your implementation return -1; } }