The problem requires finding the minimum number of coins needed to make up a given
amount.
We use a
dynamic programming
to solve this.
Create a
2D array 't'
where
t[i][j]
represents the minimum number of coins required to make amount
'j'
using the first
'i'
coins.
We
initialize the array
such that if no coins are available, the required
number of coins is infinite.
If the amount is zero, no coins are needed.
We then
fill the table
by considering whether to include or exclude each coin, ensuring we always choose the minimum number
of coins.
class Solution { // Minimum coins need to make the amount public int coinChange(int[] coins, int amount) { int noOfCoins = coins.length; int[][] t = new int[noOfCoins+1][amount+1]; int infinite = (int)1e9; // If number of coins is zero then theoretically, no. of coins // required to make the amount = infinite for(int i=0;i<=amount;i++) t[0][i] = infinite; // If Amount is zero then number Of coins required to make the amount = 0 for(int i=0;i<=noOfCoins;i++) t[i][0] = 0; for(int i=1;i<=noOfCoins;i++){ for(int j=1;j<=amount;j++){ if(coins[i-1]>j) // Coin's value is greater the amount t[i][j] = t[i-1][j]; else t[i][j] = Math.min(t[i-1][j],1 + t[i][j-coins[i-1]]); } } if(t[noOfCoins][amount]==infinite) return -1; else return t[noOfCoins][amount]; } }
The algorithm iterates through each coin and each possible amount, resulting in a time complexity of O(n * amount).
The algorithm uses a 2D array of size (n+1) x (amount+1) to store intermediate results.