Coin change with Dynamic Programming

I believe the names alone aren't the problem with this code. The problem is that your classes are too mutable, and don't do what you expect from the name.

From a class called Coin I expect it to represent a single coin. Not a stack of same-valued coins. Same with a class called Sum. I expect it to represent a total value of a bunch of coins, in this context it might even hold that bunch of coins. But I don't expect it to have it's bunch of coins changed from outside, and with a different method update to the sum of those coins.

To fix this we're going to have to overhaul your entire program structure I'm afraid.

Let's start by changing the Coin class to become an immutable representation of a single coin piece.

public class Coin {
    private final int value;

    public Coin(int value){
         this.value = value;
    }

    public int getValue(){
        return value;
    }
}

Now this class looks almost too stupid to exist. We can represent the coins in our program with simple int's and everything will work. The reason to use this class instead of an int is to make it explicit that we're talking about a Coin.

An added bonus is that we can also include a specific toString() method that makes a distinction between 'cents' and 'dollars' for example (depends on the currency you want to use).

public String toString(){
    if((value/100 > 0) && (value % 100 == 0)){
        return (value/100) + "$";
    }
    return value + "cent";
}

The next thing we need is a representation of 'a bunch of coins'. Let's call this Change. This class will cointain which coins are used in that specific 'change' and the total value of said change. It would be nice if this class was immutable as well.

public class Change {
    private int totalValue;
    private List<Coin> coins;

    private Change(int total, List<Coin> coins) {
        this.totalValue = total;
        this.coins = Collections.unmodifiableList(coins);
    }

    public static Change createEmptyInstance(){
        return new Change(0, Collections.<Coin>emptyList()); 
    }

    public Change addCoin(Coin coin){
        List<Coin> newCoins = new ArrayList<>(coins.size()+1);
        newCoins.addAll(coins);
        newCoins.add(coin);
        return new Change(totalValue + coin.getValue(), newCoins);
    } 

    public int getValue(){
        return totalValue;
    }

    public List<Coins> getCoins(){
        return coins;
    }

    /**
    * returns the number of coin pieces used in this change.
    */
    public int getNumberOfcoins(){
        return coins.size();
    }
}

Notice how the only 2 ways of getting a new Change are by starting from a new empty instance and by adding a coin to an existing instance. Adding here means creating a new instance that holds all the coins from the previous one, plus the new coin. Thus the previous instance remains unchanged.

Now for the CoinChange class. Let's first look at the responsibility of the class. The main purpose is, given a set of coins, find the correct change for a certain total value with the minimal amount of coins.

Since the main purpose is to calculate something, let's rename the class to CoinChangeCalculator.

Next my explanation says "given a set of coins". This sounds like a set of coins is passed in through the constructor. It's a "given" for an instance of the class.

We also want it to return the change for a certain total value. So let's add a method that does exactly that.

public class CoinChangeCalculator {
    //once the calculator is instantiated with a set of coins this set never changes.
    private final List<Coin> coinSet;

    public CoinChangeCalculator(List<Coin> coins){
        this.coinSet = Collections.unmodifiableList(coins);
    }

    public Change getChangeFor(int totalAmount){
        //TODO implement
    }
}

Now for the actual implementation. You have chosen to go with dynamic programming. This means we'll keep track of all minimal Change solutions below the wanted value. Let's stick with your choice of an array, but rename it to something apropriate for this class. And also instantiate it with the empty Change for value 0;

private Change[] minimalChanges = new Change[]{Change.createEmptyInstance()};

Now we can implement the method to getChangeFor(int totalAmount) as follows:

public Change getChangeFor(int totalAmount){
    calculateChangeUpTo(totalAmount);
    return minimalChanges[totalAmount];
}

This means we ensure the minimalChange for totalAmount is pre-calculated and then return the known minimal Change. The next time we call this method for an amount smaller or equal to this amount we don't need to calculate it again.

Now for the actual implementation. We're going to follow the same strategy that you used.

1) Loop over all (unknown) amounts from 0 till the wanted amount.
2) For each Coin, if it's smaller than the required amount: add this Coin to the corresponding smaller Change that gives the wanted amount.
3) Check if this Change is the current smallest known Change for that amount

This results in the following code

//step 1
private void calculateChangeUpTo(int amount){
    if(minimalChanges.length > amount){
        //already calculated before. Don't need to do anything.
        return;
    }

    //keep track from which index we need to calculate new values.
    int knownChangeIndex = minimalChanges.length-1;
    //ensure our new array is long enough
    Change[] newMinimalChanges = new Change[amount+1];
    //keep the previously calculated Changes
    System.arraycopy(minimalChanges, 0, newMinimalChanges, 0, minimalChanges.length);
    minimalChanges = newMinimalChanges;

    for(int i = knownChangeIndex+1 ; i <= amount ; i++){
        safeCalculateChangeFor(i);
    }
}

//step 2
private void safeCalculateChangeFor(int amount) {
    for(Coin coin : coinSet){
        if(coin.getValue() <= amount){
            Change newChange = minimalChanges[amount - coin.getValue()].addCoin(coin);
            updateChangeFor(amount, newChange);
        }
    }
}

//step 3
private void updateChangeFor(int amount, Change change){
    if(minimalChanges[amount] == null) {
        minimalChanges[amount] = change;
        return;
    }

    if(change.getNumberOfcoins() < minimalChanges[amount].getNumberOfcoins()){
        minimalChanges[amount] = change;
    }
}

note that I called the second method safeCalculateChangeFor because this assumes the minimalChanges array is long enough for the new change and the previous values are already calculated. It might also be a good idea to add this in a comment on the method.

And we're done ... or are we?

There is one last problem with the new code up to now. And that is if a certain change can't be given with the Coins. For example, if we only have a Coin with value 2 cents, we can't give change of 1 cent.

You solved this yourself by setting the count to Integer.MAX_VALUE. This alone won't work on my new solution since we're adding 1 to the count of a previously calculated Change. If that's already an impossible Change the program will try to store Integer.MAX_VALUE + 1 into an integer, with results in an overflow.

To solve this in a clean way let's add a special kind of Change. One that represents an impossible Change. We can do this with a subclass of Change. And adding a factory method similar to createEmptyInstance() in the Change class. Our new Change.java file will look like this now:

public class Change {
    private int totalValue;
    private List<Coin> coins;

    private Change(int total, List<Coin> coins) {
        this.totalValue = total;
        this.coins = Collections.unmodifiableList(coins);
    }

    public static Change createEmptyInstance(){
        return new Change(0, Collections.<Coin>emptyList());
    }

    public static Change createImpossibleChange(int value){
        return new ImpossibleChange(value, Collections.<Coin>emptyList());
    }

    public Change addCoin(Coin coin){
        List<Coin> newCoins = new ArrayList<>(coins.size()+1);
        newCoins.addAll(coins);
        newCoins.add(coin);
        return new Change(totalValue + coin.getValue(), newCoins);
    }

    public int getValue(){
        return totalValue;
    }

    public List<Coin> getCoins(){
        return coins;
    }

    /**
     * returns the number of coin pieces used in this change.
     */
    public int getNumberOfcoins(){
        return coins.size();
    }

    @Override
    public String toString(){
        return coins.stream().map(Object::toString).collect(Collectors.joining(","));
    }

    private static class ImpossibleChange extends Change {
        public ImpossibleChange(int total, List<Coin> coins) {
            super(total, coins);
        }

        @Override
        public Change addCoin(Coin coin) {
            return new ImpossibleChange(getValue() + coin.getValue(),getCoins());
        }

        @Override
        public int getNumberOfcoins() {
            return Integer.MAX_VALUE;
        }

        @Override
        public String toString() {
            return "No change possible for "+getValue();
        }
    }
}

I have chosen to have the getCoins() method just return an empty list. An alternative would be to override this method as well and throw a specific error.

Now the last thing we need to change is in our CoinChangeCalculator class to set the calculated change for an impossible amount to this new ImpossibleChange.

private void safeCalculateChangeFor(int amount) {
    for(Coin coin : coinSet){
        ... same as before
    }

    if(minimalChanges[amount] == null) {
        minimalChanges[amount] = Change.createImpossibleChange(amount);
    }
}

The only thing left is to update the test classes so they work with the new code. And test if we missed some edge cases. But I'll leave that up to you.