Leet Code 322. Coin Change

 https://leetcode.com/problems/coin-change/

package pep.Day86;

import java.util.Arrays;

public class LeetCode_322_Coin_Change {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amt = 11;

        System.out.println(coinChangeRecursion(coins, amt));
        System.out.println(coinChangeMemo(coins, amt, new int[amt + 1]));
        System.out.println(coinChangeTabulation(coins, amt, new int[amt + 1]));
    }

    public static int coinChangeRecursion(int[] coins, int amt) {
        if (amt < 0)
            return -1;
        if (amt == 0)
            return 0;
        int min = Integer.MAX_VALUE;

        // sab coins ko mauka denge
        for (int coin : coins) {
            int x = coinChangeRecursion(coins, amt - coin);
            if (x >= 0 && x < min) {
                min = x + 1;    // count for current coin
            }
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    public static int coinChangeMemo(int[] coins, int amt, int[] dp) {
        if (amt < 0)
            return -1;
        if (amt == 0)
            return 0;

        if (dp[amt] != 0)
            return dp[amt];

        int min = Integer.MAX_VALUE;

        // sab coins ko mauka denge
        for (int coin : coins) {
            int x = coinChangeMemo(coins, amt - coin, dp);
            if (x >= 0 && x < min) {
                min = x + 1;    // count for current coin
            }
        }

        return dp[amt] = min == Integer.MAX_VALUE ? -1 : min;
    }

    public static int coinChangeTabulation(int[] coins, int amt, int[] dp) {
        Arrays.fill(dp, (int) 1e9);
        dp[0] = 0;
        for (int i = 0; i <= amt; i++) { 
            for (int coin : coins) {

                if (i - coin >= 0)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

            }
        }

        if (dp[amt] != (int) 1e9)
            return dp[amt];
        return -1;

    }

}