# Coin change with Dynamic Programming

I have made an implementation of coin change problem solved with Dynamic Programming. Could you guys help with renaming some method and variables?

Here is my implementation -

public class CoinChange {

public int computeMinimumNumberOfCoins(int[] coins, int finalSum) {
Sum[] sums = new Sum[finalSum + 1];
for (int i = 0; i <= finalSum; i++) {
sums[i] = new Sum(i, coins);
}

for (int i = 1; i <= finalSum; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
if (sums[i - coins[j]].getMinCoins() + 1 < sums[i].getMinCoins()) {
changeMinCoins(sums[i - coins[j]], sums[i]);
changeCoinCount(sums[i - coins[j]], sums[i], coins[j]);
}
}
}
}
return sums[finalSum].getMinCoins();
}

private void changeCoinCount(Sum from, Sum to, int coin) {
List<Coin> fromCoins = from.getCoins();
List<Coin> toCoins = to.getCoins();
for (int i = 0; i < fromCoins.size(); i++) {
Coin fromCoin = fromCoins.get(i);
Coin toCoin = toCoins.get(i);
if (toCoin.getValue() == coin) {
toCoin.setCount(fromCoin.getCount() + 1);
} else {
toCoin.setCount(fromCoin.getCount());
}
}
}

private void changeMinCoins(Sum from, Sum to) {
to.setMinCoins(from.getMinCoins() + 1);
}
}


the model classes Coin and Sum are as follows -

public class Coin {
private int value;
private int count;

Coin(int value, int count) {
this.value = value;
this.count = count;
}

public int getValue() {
return value;
}

void setValue(int value) {
this.value = value;
}

public int getCount() {
return count;
}

public void setCount(int count) {
this.count = count;
}

@Override
public String toString() {
return "Value: " + value + ", count: " + count;
}
}

public class Sum {
private List<Coin> coins;
private int value;
private int minCoins;

public Sum(int value, int[] coins) {
this.value = value;
this.coins = new ArrayList<>(coins.length);
for (int i = 0; i < coins.length; i++) {
}
if (value == 0) {
minCoins = 0;
} else {
minCoins = Integer.MAX_VALUE;
}
}

public int getValue() {
return value;
}

public int getMinCoins() {
return minCoins;
}

public void setMinCoins(int minCoins) {
this.minCoins = minCoins;
}

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

}


I have tested it with this -

import junitparams.JUnitParamsRunner;
import junitparams.Parameters;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.junit.MatcherAssert.assertThat;

@RunWith(JUnitParamsRunner.class)
public class CoinChangeTest {

CoinChange coinChange;

private Object[] coinChangeValues() {
return new Object[]{
new Object[]{new int[]{5, 10, 25}, 30, 2},
new Object[]{new int[]{9, 6, 5, 1}, 11, 2},
new Object[]{new int[]{1, 2, 3}, 5, 2},
new Object[]{new int[]{1, 3, 5}, 11, 3},
new Object[]{new int[]{1, 5, 10, 20, 25}, 40, 2},
new Object[]{new int[]{5, 10, 20, 25, 50}, 90, 3}
};
}

@Before
public void setUp() throws Exception {
coinChange = new CoinChange();
}

@Test
@Parameters(method = "coinChangeValues")
public void computeMinimumNumberOfCoins(int[] coins, int sum, int count) throws Exception {
assertThat(coinChange.computeMinimumNumberOfCoins(coins, sum), is(count));
}

}


and it seems to run fine. Here is the build.gradle file of the project above-

group 'org.yadavvi'
version '1.0-SNAPSHOT'

apply plugin: 'java'

sourceCompatibility = 1.8

repositories {
mavenCentral()
}

dependencies {
testCompile group: 'org.hamcrest', name: 'hamcrest-junit', version: '2.0.0.0'
testCompile group: 'pl.pragmatists', name: 'JUnitParams', version: '1.0.6'
testCompile group: 'junit', name: 'junit', version: '4.12'
}


I am not so sure about the names of the model classes being Coin and Sum. Also, I don't think that the changeCoinCount() and changeMinCoins() should have Sum from and Sum to as arguments.

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());
}

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

public int getValue(){
}

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());
}

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

public int getValue(){
}

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
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.