class Solution {
public:
    int helper(vector<int>& coins, int amount, unordered_map<int, int>& myHash){
        if(amount==0){
            myHash[amount]=0;
            return 0;
        }
        if(amount<0)
            return -1;
        if(myHash[amount]!=0)
            return myHash[amount];
        
        int minv = INT_MAX;
        for(int i=0; i<coins.size(); i++){
            int tmp = helper(coins, amount-coins[i], myHash);
            minv = tmp==-1? minv:min(minv, tmp+1);
        }
        
        myHash[amount]=minv==INT_MAX? -1:minv;
        return myHash[amount];
    }

    int coinChange(vector<int>& coins, int amount) {
        if(coins.empty())
            return -1;
        if(amount==0)
            return 0;
        unordered_map<int, int> myHash;
        int res = helper(coins, amount, myHash);
        return res==INT_MAX? -1:res;
    }
};