Algorithms Challenge (2) Combination Coin Change - Different coins added up to a given amount

Danny — Mon, 19 Sep 2022 01:29:22 +0000

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);
    }

}

Algorithms Challenge (1) How to print out Fibonacci series in two lines code

Danny — Fri, 16 Sep 2022 20:26:00 +0000

Print out Fibonacci numbers in range 0 - 100

Concept : print out two numbers every time

Code in java:

public class fibonacci {
   public static void main(String[] args) {
         for(int a = 0, b=1; a < 100 ; a+=b, b+=a)
             System.out.println(a + "," + (b<100 ? b + ",": ""));
    }
}

Result :
0,1,
1,2,
3,5,
8,13,
21,34,
55,89,

DEV Community: Danny

Algorithms Challenge (2) Combination Coin Change - Different coins added up to a given amount

Algorithms Challenge (1) How to print out Fibonacci series in two lines code