(UVA) Let Me Count The Ways - Solution

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

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 = {1,5,10,25,50};
    public long[][] matrix;
   
    public long coinChange(int money, int indexCoins) {
        if (money == 0) {
            return 1;
        }
        else if (money < 0 || indexCoins < 0) {
            return 0;
        }
       
        if (matrix[money][indexCoins] != -1) {
            return matrix[money][indexCoins];
        }
       
        long use = coinChange(money-coins[indexCoins], indexCoins);
        long notUse = coinChange(money, indexCoins-1);
        matrix[money][indexCoins] = use+notUse;
        return matrix[money][indexCoins];
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        matrix = new long[30001][coins.length];
        for (int i = 0; i < 30001; i++) {
            for (int j = 0; j < coins.length; j++) {
                matrix[i][j] = -1;
            }
        }
       
        String line = br.readLine();
        while (line != null) {
            int number = Integer.parseInt(line);
           
            long result = coinChange(number, coins.length-1);
       
            if (result == 1) {
                bw.write("There is only " + result + " way to produce " + number + " cents change.\n");
                line = br.readLine();
                continue;           
            }
           
            bw.write("There are " + result + " ways to produce " + number + " cents change.\n");
            line = br.readLine();
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}