import java.util.HashMap;

class Solution {
    HashMap<Integer, HashMap> memo;
    int[] coins;
    int array_sum;

    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        this.memo = new HashMap<Integer, HashMap>();
        for (int i = 0; i < coins.length; ++i) array_sum += coins[i];
        int return_val = dp(0, amount);
        return (return_val == array_sum + 1) ? -1 : return_val;
    }

    public int dp(int idx, int amount)  {
        if (memo.containsKey(idx))  {
            HashMap<Integer, Integer> hm = memo.get(idx);
            if (hm.containsKey(amount))  {
                return hm.get(amount);
            }
        }
        if (amount == 0) return 0;
        if (amount < 0 || idx == coins.length) return array_sum + 1;

        int take_coin = 1 + dp(idx, amount - coins[idx]);
        int leave_coin = dp(idx+1, amount);
        int return_val = Math.min(take_coin, leave_coin);
        if (!memo.containsKey(idx)) {
            memo.put(idx, new HashMap<Integer, Integer>());
        }
        HashMap<Integer, Integer> hm = memo.get(idx);
        hm.put(amount, return_val);
        return return_val;
    }
}