Question :
There are {1, 2 , 5} dollar types coins for selection. Use different combinations of these types coins to adding up to the given amount 50.
Answer:
We can use different types of dynamic programming methods to solve this problem. In this article , we choose to use Dynamic programming - Bottom up method.
The implementation logic is simple like this :
- Set combinations as an array , its size is "amount +1"
- combinations[0] = 1 , it means the first combination ways number is 1
- We can loop the coins into the combinations array. When the amount(the value in the position of the combinations array) is greater than coin , then we can use the formular : combinations[amount] += combinations[amount - coin];
Code:
public class coinsCombinationWays {
static int getTotalWays(int[] coins, int amount){
int[] combinations = new int[amount + 1];
combinations[0] = 1;
for(int coin: coins) {
for(int j=1; j<combinations.length; j++){
if(j>=coin)
combinations[j] += combinations[j-coin];
}
}
return combinations[amount];
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount= 50;
int totalWays += getTotalWays(coins, amount);
System.out.println(totalWays);
}
}
Top comments (1)
Looks like the Big O complexity is O(n)