(Hacker Rank) The Coin Change Problem - Solution

Link to the problem: https://www.hackerrank.com/challenges/coin-change

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


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static int[] coins;
    public static long[][] matrix;

    public static 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 static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int numCoins = sc.nextInt();
        coins = new int[numCoins];
        for (int i = 0; i < numCoins; i++) {
            coins[i] = sc.nextInt();
        }
       
        matrix = new long[money+1][numCoins];
        for (int i = 0; i < money+1; i++) {
            for (int j = 0; j < numCoins; j++) {
                matrix[i][j] = -1;
            }   
        }
       
        System.out.println(coinChange(money, numCoins-1));
    }
}