Coin Changing Minimum Count Number of Coins With a Sum Using Dynamic programming.
The question is given coins of certain denominations and a total, how many minimum coins would you need to make this total.
public class MinCoinChangeProblem {
private static int min(int a, int b) {
return a<b?a:b;
}
public static void main(String[] args) {
int[] coins = new int[] {0, 1, 5, 6, 8};
int total = 11;
int[][] dp = new int[coins.length][total+1];
for(int i=0;i<coins.length;i++) {
for(int j=0;j<total+1;j++) {
if(j==0)
dp[i][j]=0;
else if(i==0)
dp[i][j]=Integer.MAX_VALUE;
else if(j<coins[i]) {
dp[i][j]=dp[i-1][j];
}
else {
dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1);
}
}
}
System.out.println(dp[coins.length-1][total]);
}
}
The time complexity of the solution is n*m. where n is the total number of different coins available and m is the total sum required.
