Coin Change Challenge

In celebration of planning thoughtful gifts for upcoming holidays, you are tasked with solving a classic dynamic programming problem. Given an array of distinct coin denominations and a total amount, determine the fewest number of coins needed to make up that amount. If it is not possible to create the total, return -1.

Problem Statement

You are given two inputs:

• An array coins where each element represents a coin denomination.
• An integer amount representing the total amount of money.

Implement a function that returns the minimum number of coins required to sum up to the provided amount. If the amount cannot be made up by any combination of the coins, the function should return -1.

Example

Input:

coins = [1, 2, 5]
amount = 11

Output:

3

Explanation: 11 can be made with three coins: 5 + 5 + 1.

Constraints

• The length of coins is less than 100.
• Each coin denomination is a positive integer.
• amount is a non-negative integer.

Approach

A dynamic programming approach can be used to build a table that records the minimum number of coins needed for each amount from 0 up to the target amount. Use this table to iteratively compute the result for the final amount.

Happy coding on this day (2025-02-12)! Enjoy solving and refining your dynamic programming skills.