/*
Runtime: 21 ms, faster than 22.54% of Java online submissions for Coin Change. :-(
Memory Usage: 36.1 MB, less than 94.08% of Java online submissions for Coin Change.
*/
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0 ) return amount > 0 ? -1: 0;
        if (amount == 0) return 0;

        int[] cache = new int[amount + 1];
        return change(coins, cache, amount);
    }

    private int change(int[] coins, int[] cache, int amount) {
        if (cache[amount] != 0) {
            return cache[amount];
        }

        int result = -1;
        int candidate;

        for (int i = 0; i < coins.length; i++) {
            if (amount < coins[i]) {
                continue;
            }

            int rest = amount - coins[i];

            if (rest > 0) {
                int restCount = change(coins, cache, rest);

                candidate = (restCount > 0) ? restCount + 1: -1;
            } else {
                candidate = 1;
            }

            if (candidate != -1 && (candidate < result || result == -1)) {
                result = candidate;
            }
        }

        cache[amount] = result;
        return result;
    }
}