Solve Coin Change problem in Java

In this tutorial, we are looking forward to solving one of the most frequently asked interview problems ” The coin change” using dynamic programming.

Solving the coin change problem using an efficient approach in Java

In the dynamic programming approach, we use additional space complexity dp[amount+1] and store the previous results. We take a coin and start storing the number of coins required to make up a certain amount ( by iterating up to the original amount). We then keep updating the dp[i] with the current minimum of coins required and coins required using the certain coin. Then just check if some results have reached dp[amount] and if not we return -1 stating that it is not possible to make up that amount.

Let us write the code for this.

import java.util.*;

public class Main {

    public static void main(String args[]) {
        int coins[] = { 1, 2, 5};
        int amount = 11;

        int dp[] = new int[amount+1];
        dp[0] = 0;

        for(int i = 1; i <= amount; i++){
            dp[i] = amount+1;
        }

        for(int coin : coins){
            for(int amt = 1; amt <= amount ; amt++){
                if(amt >= coin){
                    dp[amt] = Math.min(dp[amt], 1 + dp[amt - coin]);
                }
            }
        }
        int minCoinsReq = dp[amount] != amount+1 ? dp[amount] : -1 ; 

        System.out.println("Minimum Coins required : " + minCoinsReq);
    }
}
Output :
Minimum Coins required : 3

In the code above, we just created an array to keep which amounts can be summed up by any coin and the minimum number of coins required to reach it. Repeating this for each coin we can reach how many minimum coins are required to gather a particular amount. Hence we reach our solution.

If any doubts mention below.

Leave a Reply

Your email address will not be published. Required fields are marked *