Q22 Coin Change II - LeetCode 518

class Solution {
    //Q21
    public int change(int amount, int[] coins) {
        int n = coins.length;
        // return solve(coins , n-1 , amount , new Integer[n][amount+1]);

        //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++){
                if(i == 0){
                    if(j%coins[i] == 0)
                    dp[i][j] = 1;

                    else
                    dp[i][j] = 0;
                }
                else{
                     int notake = dp[i-1][j];
                    int take = 0;
                    if(j - coins[i] >= 0)
                    take = dp[i][j-coins[i]];

                    dp[i][j] = take + notake;
                }
            }
        }
        return dp[n-1][amount];
    }

    /* by trying each coin on amount multiple times we get combonition as no coin gets 
    repeated
        by trying all coins on amount multiple times we get permutation as coins gets
        repeated
    */
    //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 1;

            else
            return 0;
        }
        if(dp[i][amt] != null)
        return dp[i][amt];
        
        //faith calls for all ways if we take or not take from next level
        int notake = solve(coins , i-1 , amt , dp);
        int take = 0;
        if(amt - coins[i] >= 0)
        take = solve(coins , i , amt  - coins[i] ,dp);

        return dp[i][amt] = take + notake;
    }
}