Minimum Coin Change

In this challenge, you'll solve the coin change problem using dynamic programming. Given an array of coin denominations and a target amount, your task is to determine the minimum number of coins required to make up that amount. If the amount cannot be reached with the given denominations, return -1.

Problem Statement

• You are given an integer array called coins where each element represents a coin denomination.
• You are also given an integer amount representing the total amount of money.

Write a function that returns the fewest number of coins needed to make up that amount. If it is not possible to reach the amount with the given coins, return -1.

Example

For example, given coins = [1, 2, 5] and amount = 11, the output should be 3 because 11 can be made with 5 + 5 + 1.

Hints

• Use dynamic programming to build a solution from the smallest subproblems.
• Consider an array dp where dp[i] holds the minimum coins needed for amount i.
• Initialize dp[0] as 0 and the rest as a large value (e.g., amount + 1).

Happy coding on this inspiring day that reminds us to pursue equality and progress—values celebrated on Martin Luther King Jr. Day!