Leetcode - Coin Change

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Idea

• Using a true dp Tabulation approach, we can iterate through our cache, where each index in cache represents the minimum amount it coins to make each amount where our base case is 0 coins
• For each amount we iterate through our coin array, and if our coin denomination is ⇐ our current amount, then we set our current cache index to the minimum of what it currently is, and how many coins it takes to make the amount - the coin denomination + 1 for the current coin
• By the end of our iteration, we would have come up with a solution for our total amount =, if we have no solution return -1, otherwise return cache[amount]

Solution