Given an integer total that represents the target amount of money and a list of integers coins that represents different coin denominations, find the minimum number of coins required to make up the total amount. If it’s impossible to achieve the target amount using the given coins, return -1. If the target amount is 0, return 0.

Note: You can assume that we have an infinite number of each kind of coin.

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

The naive approach is to generates all possible combinations of given denominations such that in each combination, the sum of coins is equal to total. From these combinations, choose the one with the minimum number of coins and return the minimum number required. If the sum of any combinations is not equal to total then print -1.

In the worst case, the time complexity increases exponentially with the total amount, which results in an algorithm edging toward $O(n^{total})$. The space complexity is $O(total)$ because the maximum depth of the recursion tree grows up to total. We can't improve the space complexity, but we can definitely improve our time complexity if we use dynamic programming to solve this problem.

If we look at the problem, we might immediately think that it could be solved through a greedy approach. However, if we look at it closely, we’ll know that it’s not the correct approach here. Let’s take a look at an example to understand why this problem can’t be solved with a greedy approach.

Let's suppose we have coins = [1, 3, 4, 5] and we want to find the total = 7 and we try to solve the problem with a greedy approach. In a greedy approach, we always start from the very end of a sorted array and traverse backward to find our solution because that allows us to solve the problem without traversing the whole array. However, in this situation, we start off with a 5 and add that to our total. We then check if it’s possible to get a 7 with the help of either 4 or 3, but as expected, that won't be the case, and we would need to add 1 twice to get our required total.

The problem seems to be solved, and we have concluded that we need maximum 3 coins to get to the total of 7. However, if we take a look at our array, that isn’t the case. In fact, we could have reached the total of 7 with just 2 coins: 4 and 3. So, the problem needs to be broken down into subproblems, and an optimal solution can be reached from the optimal solutions of its subproblems.

To split the problem into subproblems, let's assume we know the number of coins required for some total value and the last coin denomination is C. Because of the optimal ...