Find Minimum Number of Coins to Make a Given Value (Coin Change)

In this article, we will solve the problem of finding the minimum number of coins needed to make a given value.

Problem Statement: We are given iven an array coins[] of size N and a target value V, where coins[i] represents different coin denominations. So over here our job  task is to find out  the minimum number of coins required to make the given value V.

Examples:

Input: coins[] = {1, 3, 4}, V = 6 Output: Minimum 2 coins required. We can use two coins of 3 units each.

Input: coins[] = {2, 5, 10, 1}, V = 27 Output: Minimum 4 coins required. We can use two coins of 10 units, one coin of 5 units, and two coins of 1 unit.

Input: coins[] = {7, 5, 1}, V = 9 Output: Minimum 2 coins required. We can use one coin of 7 units and one coin of 2 units.

Solution:

To solve this problem, we will follow these steps:

Steps to Solve:

1.    Initialize the DP Array:

o   Create an array dp[] of size V + 1 and initialize all values to V + 1 (an impossible high value).

o   Set dp[0] to 0 because zero coins are needed to make the value 0.

2.    Fill the DP Array:

o   For each coin in the coins[] array, update the dp[] array.

o   For each value from the coin's denomination up to V, update the dp value to the minimum of its current value or 1 + dp[value - coin].

3.    Return the Result:

o   If dp[V] is still V + 1, return -1 because it's not possible to make the value V with the given coins.

o   Otherwise, return dp[V].

Time Complexity: O(N * V)

Space Complexity: O(V)