Q-20 Coin Change - LeetCode 322

class Solution {
    //Q-20
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        if(amount == 0)
        return 0;

        // int ans = solve(coins ,n-1 ,  amount , new Integer[n][amount+1]);
        // return ans >= (int)1e9 ? -1 : ans;

        //tabulization -> n*amt | sc- n*amt
        int dp[][]  = new int[n][amount+1];
        for(int i = 0 ;i < n ;i++){
            for(int j = 0 ;j < amount+1 ;j++){
                //base case
                if(i == 0){
                    if(j%coins[i] == 0)
                    dp[i][j] = j/coins[i];

                    else
                    dp[i][j] = (int) 1e9;
                }

                //recursion logic
                else{
                    int notake = 0 + dp[i-1][j];
                    int take = (int) 1e9;
                    if(j - coins[i] >= 0)
                    take = 1 + dp[i][j-coins[i]];

                    dp[i][j] = Math.min(take , notake);
                }
            }
        }
        //if >= 1e9 , return -1
        return dp[n-1][amount] >= (int)1e9 ? -1 : dp[n-1][amount];
    }
    /* in any question where it is mentioned infinite supply or multiple use , one of the 
    recursion calls will not reduce index , as we have to check it again and again till
    its invalid
    */
    //Recursion-> exponential(can't determine no. of options) | 
    //Memoization -> n*amt Sc-> n*amt + amt(stack height)
    public int solve(int coins[] , int i ,int amt , Integer[][] dp){
        if(i == 0){
            if(amt % coins[i] == 0)
            return amt/coins[i];

            else
            return (int) 1e9;
        }
        if(dp[i][amt] != null)
        return dp[i][amt];

        int notake = 0 + solve(coins , i-1 , amt , dp);
        int take = (int) 1e9;
        if(amt - coins[i] >= 0)
        take = 1 + solve(coins , i , amt  - coins[i] ,dp);

        return dp[i][amt] = Math.min(take , notake);
    }
}