/*
Runtime: 26 ms, faster than 20.24% of Java online submissions for Coin Change. :-(
Memory Usage: 36 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;
        for (int i = 0; i < coins.length; i++) {
            int rest = amount - coins[i];
            if (rest > 0) {
                int num = change(coins, cache, rest);
                if (num != -1 && (num < result || result == -1)) {
                    result = num + 1;
                }
            } else if (rest == 0) {
                result = 1;
            }
        }

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