(UVA) Exact Change - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2512

The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public int[] coins;
    public State[][] matrix;
  
    public State coinChange(int money, int indexCoins) {
        if (money <= 0) {
            //System.out.println("return: " + money*(-1) + " " + numMoneyUsed);
            return new State(money*(-1), 0);
        }
        else if (indexCoins < 0) {
            return new State(Integer.MAX_VALUE/2, Integer.MAX_VALUE/2);
        }
      
        if (matrix[money][indexCoins] != null) {
            return matrix[money][indexCoins];
        }
      
        //System.out.println("used: " + coins[indexCoins]);
        State use = coinChange(money-coins[indexCoins], indexCoins-1);
        use = new State(use.money, use.numMoney+1);
        State notUse = coinChange(money, indexCoins-1);
        //notUse = new State(notUse.money, notUse.numMoney);
        if (use.money < notUse.money) {
            matrix[money][indexCoins] = use;
        }
        else if (use.money > notUse.money) {
            matrix[money][indexCoins] = notUse;
        }
        else {
            if (use.numMoney < notUse.numMoney) {
                matrix[money][indexCoins] = use;
            }
            else {
                matrix[money][indexCoins] = notUse;
            }
        }
        return matrix[money][indexCoins];
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        matrix = new State[10001][100];
      
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            for (int k = 0; k < 10001; k++) {
                for (int j = 0; j < 100; j++) {
                    matrix[k][j] = null;
                }
            }
            int money = sc.nextInt();
          
            int billsCoins = sc.nextInt();
            coins = new int[billsCoins];
            for (int j = 0; j < billsCoins; j++) {
                coins[j] = sc.nextInt();
            }
          
            State answer = coinChange(money, billsCoins-1);
            //System.out.println(answer.money);
            bw.write((money+answer.money)+" "+answer.numMoney+"\n");
        }
              
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}

class State {
    int money;
    int numMoney;
  
    public State(int m, int nM) {
        money = m;
        numMoney = nM;
    }
}