Coin Change Problem 1 & 2.

What is a coin change problem?
There are two types in this, almost similar:-
1.) Minimum number of coins- Coin Change 1 on Leetcode
2.) Maximum number of ways- Coin Change 2 on Leetcode

So, we have been given a coins array which consists of different denominations of the coins, and a total amount.

1. Coin Change- 1
Here you need to find the minimum number of coins needed to make the amount.

We are choosing bottom-up approach here, which is mainly using arrays , 1d or 2d.

1. We will initialise an array, say dp[] of size= amount+1.
2. dp[0]=0, since you need 0 coins for 0 amount.
3. So, if 1 was present in the coin, you will get (1-1=0), dp[0]=0, now add 1, =1, 1 exists in the coins.
4. Every other number less than the amount(11) is a subproblem, you find minimum number of coins for every subproblem, imagining that it is the amount you need, and you eventually find for the last number that is the amount.

class Solution {
    public int coinChange(int[] coins, int amount) {
        
        int n=coins.length;
        int dp[]=new int[amount+1];
        dp[0]=0;
        for(int i=1; i<=amount;i++)
        {
            dp[i]=amount+1;
        }
        for(int i=1; i<=amount; i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i>=coins[j])
                {
                    dp[i]=Math.min(dp[i-coins[j]]+1, dp[i]);
                }
                
            }
            System.out.println(dp[i]);
        }
        if(dp[amount]==amount+1 && dp[1]!=1)
            return -1;
        return dp[amount];
    }
}

5. When no combination of coins sums upto the amount, you return -1, when 1 is present you will get any n number with n combinations of 1. hence the condition above.

2. Coin Change-2
Here you need to find the maximum number of ways , you can make the amount

1. We need a 2D-Array, with size length of coins, amount.
2. You initialise the first column as 1, and calculate for the first row as shown.
3. Find the maximum number of ways for every number less than amount in the matrix, and then finally for the amount.
4. if amount > coin we are using, fill the matrix with the sum of the previous row, same column and the difference amount (dp[i][j-coins[i]) in the same row.

class Solution {
    public int change(int amount, int[] coins) {
        
        int n=coins.length;
        int dp[][]= new int[n][amount+1];
        
        for(int i=0;i<n;i++)
        {
            dp[i][0]=1;
        }
        
        for(int j=1;j<=amount;j++)
        {
            if(j>=coins[0])
            dp[0][j]= dp[0][j-coins[0]];
        }
        
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<=amount;j++)
            {
               if(j>=coins[i])
               {
			   dp[i][j]= dp[i-1][j]+ dp[i][j-coins[i]]; 
                }
                else
                    dp[i][j]=dp[i-1][j];
            }
 
        }
        return dp[n-1][amount];
    }
}