#322.Coin Change [LeetCode Grind 75 in Java]

class Solution {
    //memoization dp
    public int f(int i , int tg , int[] coins , int[][] dp){
        if(i == 0){
            if(tg % coins[i] == 0) return dp[i][tg] = tg/coins[i];
            else return Integer.MAX_VALUE;
        }
        if(tg == 0) return dp[i][tg] = 0;
        if(tg < 0) return Integer.MAX_VALUE;

        if(dp[i][tg] != -1) return dp[i][tg];

        //take
        int t = f(i , tg - coins[i] , coins , dp);
        if(t != Integer.MAX_VALUE) t += 1;

        //not take
        int nt = f(i - 1 , tg , coins , dp);

        return dp[i][tg] = Math.min(t , nt);
    }

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        for(int[] r : dp) Arrays.fill(r, -1);

        f(n - 1 , amount , coins , dp);

        if(dp[n-1][amount] == Integer.MAX_VALUE) return -1;
        return dp[n-1][amount];   
    }
}