Title

class Solution {
    
    Integer[][] cache;
    public int coinChange(int[] coins, int amount) {
        cache = new Integer[amount+1][coins.length];
        
        int total = coinChangeAux(coins, amount, coins.length-1);
        if(total == Integer.MAX_VALUE)
            return -1;
        else
            return total;
    }
    
    public int coinChangeAux(int[] coins, int amount, int i) {
        if(i < 0)
            return Integer.MAX_VALUE;
        
        if(amount < 0)
            return Integer.MAX_VALUE;
        
        if(0 == amount)
            return 0;
        
        if(cache[amount][i] != null)
            return cache[amount][i];
        
        int r1 = coinChangeAux(coins, amount - coins[i], i);
        r1 = r1 == Integer.MAX_VALUE ? Integer.MAX_VALUE : 1 + r1;
        
        int r2 = coinChangeAux(coins, amount, i-1);

        cache[amount][i] = Math.min(r1, r2);
        return cache[amount][i];
    }
}