Minimum Coins
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Minimum Coins Problem (Minimum elements to reach a target sum using unlimited coin denominations), Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Greedy Algorithm, Time Complexity, Space Complexity, Arrays, Subsequences, Subset Sum, dynamic programming, memoization, tabulation, space optimization, recursion, Knapsack Problems.
Problem Statement: Given a target sum X and N distinct coin denominations, find the minimum number of coins required to reach the target sum. You can pick a coin denomination any number of times. Input Specification: The first line contains two integers N and X, representing the number of distinct coin denominations and the target sum, respectively. The second line contains N space separated integers, representing the coin denominations. Output Specification: Print a single integer, the minimum number of coins required to reach the target sum. If it is not possible to reach the target sum, print 1. Sample Test Case: Input: Output: Explanation: To make a sum of 7 with coins {1, 2, 3}, one optimal way is to use three coins: {2, 2, 3} or {1, 3, 3}.